A-礼物

该题有视频讲解，故在这里只放出代码。

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[11]={0};//一开始每个人都赚了0元
for(int i=1;i<=n;i++)
{
int s,m;
cin>>s>>m;
if(m==0) continue;//如果不给任何人送礼 直接continue 避免发生除以0的情况
//注意 若s==0 不要直接continue 会导致没有输入接下来的m个数
int t=s/m;//算出要给每个人送的钱
a[i]-=m*t;//i这个人亏了这么多钱
for(int j=1;j<=m;j++)
{
int x;
cin>>x;
a[x]+=t;//x这个人赚了t元
}
}
for(int i=1;i<=n;i++) cout<<a[i]<<endl;
return 0;
}

B-采购牛奶

思路：排序+贪心

很显然想要花费最小，就要先买最便宜的牛奶，便宜的买完了再买贵的，所以我们可以根据牛奶的价格排序（自定义com函数，如果这里不会可以先学排序部分的题目）。

排好序之后，我们以单价从低到高的顺序枚举这m个奶农。设n为我们当前还需要购买的奶量，首先要判断奶农拥有的总奶量是否比n小，如果小于等于n，我们可以全买下来，然后枚举下一个奶农；如果大于n了，就说明我们现在只需要再买n份奶就够了，所以只需要将总价格加上在该奶农手里买n份奶的价格即可。要注意每次买了奶之后要更新n的值，即用n减去奶的份数。

最后的答案就是加起来的总价格。

#include<bits/stdc++.h>
using namespace std;
int n,m,sum;
struct node
{
int price;
int all;
}milk[5010];
bool com(node a,node b)
{
return a.price<b.price; //按价格从低到高排序
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d",&milk[i].price,&milk[i].all);
sort(milk+1,milk+m+1,com);
for(int i=1;i<=m;i++) //枚举m个奶农
{
if(milk[i].all<=n) //判断拥有的奶量是否<=n
{
n-=milk[i].all; //全部买下来
sum+=milk[i].price*milk[i].all;
}
else
{
sum+=milk[i].price*n;
break;
}
}
printf("%d",sum);
return 0;
}

C-乘坐高铁

题意：给定你一个访问城市的顺序，同时给定相邻两城市间的过路费、买卡费以及买卡后的过路费，要求按顺序访问城市最少花费的价格。

思路：差分

很显然，这道题需要你抉择对于每段路而言刷卡更便宜还是买票更便宜（如果要买卡肯定是一开始就买卡，不可能买了几次票之后再去买卡），那我们只要能求出一共要走这段路几次，自然就能够知道怎样更便宜。

假设有一段路我们一共要走x次，买票要a元，买卡要c元，买卡后刷卡要b元。我们就只需要把ax和c+bx作比较，选择便宜的方法即可。

现在让我们聚焦核心问题：怎样计算出一段路我们要走几次。假设我们定义了x数组来存储这段路走的次数，x[i]表示i到i+1之间这段路一共走了几次。

以样例 3 1 4 1 5 9 2 6 5 3 为例：

第一步我们要从3走到1，所以x[1]++, x[2]++；第二步我们要从1走到4，所以x[1]++, x[2]++, x[3]++，以此类推。但显然这是在循环里套循环，简单计算发现可能超时，我们要把这个更新x数组的过程优化一下。

考虑某一次我们要从A城市走到B城市（如果A>B就交换一下AB位置，保证A<B），那么我们需要把x[A]一直到x[B-1]之间的所有x数组均+1，这样一个区间更新问题显然可以用差分解决。即定义一个差分数组cf，要实现区间+1的操作，只需要把cf[A]++, cf[B]--即可，最后再对差分数组做一遍前缀和即可得到x数组（这一段如不了解可以参考差分相关题目）。

计算出x数组后我们就可以算出每段路怎样更便宜，将走每段路需要花的钱相加即可，注意要开long long。

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,P[N],x[N],cf[N];
long long a[N],b[N],c[N],ans;//这道题数据范围较大，和答案有关的变量要开long long
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>P[i];
for(int i=1;i<=n-1;i++) cin>>a[i]>>b[i]>>c[i];
for(int i=1;i<=m-1;i++)
{
int A=P[i],B=P[i+1];//变量含义与题解内相同
if(A>B) swap(A,B);
cf[A]++;
cf[B]--;
}
for(int i=1;i<=n-1;i++) x[i]=x[i-1]+cf[i];//用前缀和的方法算出x数组
for(int i=1;i<=n-1;i++) ans+=min(a[i]*x[i],c[i]+b[i]*x[i]);
//这里枚举到n-1，因为只有n-1段路
cout<<ans;
return 0;
}

D-逛画展

思路：双指针

所谓双指针，就是一种我们在解决“选择最优区间”问题时的常用思路。

定义一个变量表示左端点，一个变量表示右端点，我们只需要不断挪动左端点和右端点使这个区间满足要求。比如这道题我们先固定左端点为1，然后不断把右端点往右移，直到包含了所有画家，再移动左端点使区间最短，如此往复即可。

具体而言，首先注意到必须看到所有的画师的画才行，所以可以考虑维护一个区间内，每个画师有多少画，可以用一个book数组来维护，book[i]表示当前选择的区间内i画家的画有几幅，而且要维护计数器cnt表示现在看到了几个画师。

首先把左端点初始化为1，把区间右端点不断右移，并不断维护画师出现次数，出现新的画师把cnt+1，直到看到所有画师的画。

然后循环判断左端点的画师是否出现一次以上，这时候应用贪心思想，只要出现过一次以上，那么左端点就一定可以弹出，因为这个点的存在只会让区间更长，而不会让区间包含画师更多，我们只要保证这个区间有每个画师的画就行了。

找到这样的区间之后便可以判断区间长度并更新最小值。

然后把左端点向右移动一格尝试找新的区间，继续把区间右端点不断右移，循环剩下的画，同样是在看到所有画师的画之后暂停循环，贪心地弹出左端点，找到一个最短的区间，更新答案，如此往复，具体见代码。

上述过程看起来比较复杂，但大家可以实际模拟一下样例，就会发现这其实也是比较简单的思想。

虽然循环嵌套，但是因为每个点都只会最多出入一次区间，所以复杂度O(n)，只是常数略大。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000010];
int book[1000010];//book[i]表示当前选择的区间内i画家的画有几幅
int cnt,l,r;//cnt表示当前选择的区间内共有几位作家的画 [l,r]表示当然选择的区间
int ansl,ansr,minn=99999999;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
l=r=1; //初始化区间为[1,1] 即只选择第一幅画
book[a[1]]=1; //a[1]为第一幅画的作家，book[a[1]]=1表示目前a[1]这个作家有一幅画在区间内
cnt++; //此时区间内有一个画家的画
while(r<=n)//如果区间超出范围就停止循环
{
if(cnt==m)//如果当前区间内已经有m个画家的画了
{
while(book[a[l]]>1) //如果区间左端点的这个画家的画不止一副，我们显然可以贪心地舍弃这幅画，让左端点++
{
book[a[l]]--; // 左端点++之前要把这个画家现在画的数量更新
l++;
}
int k=r-l+1;//当前的区间长度 即票价
if(k<minn) //由于这里是<不是<= 所以找到的答案一定是左端点最小的
{
minn=k;
ansl=l;
ansr=r;
}
//我们已经找到了当前左端点下最优的答案
//还想找更优的答案 所以把左端点++ 尝试找新的满足条件的右端点
//由于这时候左端点的画家肯定只出现过一次 所以要把cnt--
book[a[l]]--;
cnt--;
l++;
}
//在满足cnt==m之前，r要不断后移，以求包含更多的画家
r++;
if(!book[a[r]]) cnt++;
book[a[r]]++;
}
printf("%d %d",ansl,ansr);
return 0;
}