Description
Zyn 需要能量提高自己的超能力，有两种能量存在：超级能量和小能量。对于超级能量，Zyn 绝对不可以错过，而且努力的 Zyn 希望得到更多的小能量。
但是 Zyn 每天最多可以获得 k 次能量，而且每个能量都会在第 xi 天后消失，Zyn 希望你可以帮助他求出得到的小能量的最多数量。
Input
第一行包含三个正整数 n,m,k (1≤n,m≤106,1≤k≤107) 表示超级能量，小能量和每天最多可以获得能量的个数。
第二行包含 n 个整数，表示第 i 个超级能量会在第 xi (0≤xi≤107) 天消失。
第三行包含 m 个整数，表示第 i 个小能量会在第 xi (0≤xi≤107) 天消失。
Output
如果不能获得全部超级能量，输出"Zyn!"(不含引号)，否则输出可以获得的最多的小能量的数量。
Sample
Input
3 4 2
0 2 3
1 1 2 5
5 3 2
0 0 0 1 1
1 1 2
Output
4
Zyn!
Hint
题目样例为两组，由于 OJ 不支持多样例所以用回车分隔开。
样例一：可以在 44 天内获得所有小能量，
- 第 00 天：22 个超级能量
- 第 11 天：22 个小能量
- 第 22 天：11 个超级能量 + 11 个小能量
- 第 33 天：11 个小能量
总共获得 44 个小能量（33 个超级能量全部获得）
样例二：没用任何一种方法可以获得全部超级能量，输出"Zyn!"(不含引号)
考试时的思路完全错了，想得就是从前向后遍历，如果今天的超近能量大于k，则判断一下ans+k与今日超级能量的大小关系；
错误代码（当然也犯了一个致命错误，应该从0开始）
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+100;
#define endl '\n'
#define ll long long
int n,m,k;
int supper[N],small[N];
int cnt;
int cnt1[N];
int cnt2[N];
int ans;
int M;
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&supper[i]);
cnt1[supper[i]]++;
M=max(M,supper[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&small[i]);
cnt2[small[i]]++;
M=max(M,small[i]);
}
while(1)
{
if(cnt>M)
break;
int num=k;
if(cnt1[cnt]>k)
{
if(cnt1[cnt]>k+ans)
{
printf("Zyn!");
return 0;
}
else
{
if(ans>=cnt1[cnt])
ans-=cnt1[cnt];
else
{
ans=0;
num=num+ans-cnt1[cnt];
}
}
}
else
num-=cnt1[cnt];
if(num>=cnt2[cnt])
{
num-=cnt2[cnt];
ans+=cnt2[cnt];
}
else
ans+=num;
cnt++;
}
printf("%d\n",ans);
return 0;
}
根据截止时间的性质，按照截止时间从大到小的顺序依次枚举超级能量，判定每天剩余小能量的 数量，然后根据当天小能量的数量枚举可能的最大数量。
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
#define inf 0x3f3f3f3f
int a[N],b[N];
int n,m,k;
int maxa,maxb;
int cnt;
int ans;
int main()
{
cin>>n>>m>>k;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
a[x]++;
maxa=max(maxa,x);
}
for(int i=0;i<m;i++)
{
int x;
cin>>x;
b[x]++;
maxb=max(maxb,x);
}
for(int i=maxa;i>=0;i--)
{
if(a[i]>k)
{
cnt+=a[i]-k;
a[i]=k;
}
else if(a[i]<k)
{
if(cnt>=k-a[i])
{
cnt-=(k-a[i]);
a[i]=k;
}
}
}
if(cnt)//没有拿全超级能量
{
cout<<"Zyn!";
return 0;
}
cnt=0;
for(int i=maxb;i>=0;i--)
{
b[i]+=cnt;
cnt=0;
if(b[i])
{
int can=k-a[i];
if(can>=b[i])
{
ans+=b[i];
b[i]=0;
}
else
{
ans+=can;
b[i]-=can;
cnt=b[i];
b[i]=0;
}
}
}
cout<<ans<<endl;
return 0;
}
