[CSP-S模拟测试]:密州盛宴（贪心）
江城子·密州出猎
老夫聊发少年狂，左牵黄，右擎苍，锦帽貂裘，千骑卷平冈。为报倾城随太守，亲射虎，看孙郎。
酒酣胸胆尚开张，鬓微霜，又何妨！持节云中，何日遣冯唐？会挽雕弓如满月，西北望，射天狼。
（这首词通过描写一次出猎的壮观场面，借历史典故抒发了作者杀敌为国的雄心壮志，体现了为了效力抗击侵略的豪情壮志，并委婉地表达了期盼得到朝廷重用的愿望）
题目传送门（内部题29）
输入格式
输入包含多组数据，对于每组数据：
第一行包含两个正整数$n$和$m,n$的意义如上所述，$m$表示接下来的$m$行
第二行至$m+1$行，每行一个$01$串$s_i$和一个正整数$t_i$，表示这个串需要重复$t_i$次。
（保证最后的串长度为$2n$）
最后以$n=0,m=0$结束输入。
输出格式
对于每组数据：
如果有解，输出一个正整数$C$，意义如题所述。
否则输出$"-1"$（不含引号）
样例
样例输入：
5 3
1 3
0 5
11 1
样例输出：
2
数据范围与提示
样例解释：
首先初始菜品的序列为$1110000011$，那么我们将其变为$0011100011$，答案为$2$
数据范围：
$nleqslant {10}^{18},mleqslant {10}^5,t_ileqslant {10}^{18},S$的总长度$leqslant {10}^6,$数据组数$leqslant 5$。
题解
首先所有时间必须所有人都在吃菜。
显然，类型为$0$的菜品越靠前越优。并且，为$0$的菜品不能超过$n$个。从后面推，我们把为$1$的菜品设为$+1$，为$0$的菜品设为$-1$，然后从末尾开始计算后缀和。一但后缀和到了$-2$，就说明到了苏东坡没法吃菜的地步。所以说只要保证后缀和一直大于等于$-1$，那么这个就一定可以在$N$分钟内解决。
因此，我们希望每份为$1$的菜品后移$C$位，使后缀和一直不小于$-1$。
可以从末尾挑出$C$（这里为$2$）份为$0$的菜品，全部安排在开头。
计算后缀和。我们可以发现，每将一份为$0$的菜品移动到前面去，后缀和就会全部加$1$。所以说，我们只要计算整个序列中后缀和最小值是多少。每一个小段都可以算出后缀和的贡献。然后我们就可以求出这个值，假设是$-k$。那么最终答案就是$k-1$。
时间复杂度$Theta(sum S)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
long long n,m,t;
char ch[100001];
pair<long long,long long> pos[100001];
long long one,k,pre;
int main()
{
while(1)
{
memset(pos,0,sizeof(pos));
k=pre=one=0;
scanf("%lld%lld",&n,&m);
if(!n&&!m)break;
for(int i=1;i<=m;i++)
{
scanf("%s%lld",ch+1,&t);
for(int j=strlen(ch+1);j;j--)
if(ch[j]-'0')
{
one+=t;
pos[i].first++;
}
else
{
pos[i].first--;
pos[i].second=min(pos[i].second,pos[i].first);
}
pos[i].first*=t;
}
if(one<n){puts("-1");continue;}
for(int i=m;i;i--)
{
k=min(k,pos[i].second+pre);
pre+=pos[i].first;
}
printf("%lld
",max(0LL,-k-1));
}
return 0;
}
rp++