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 55 3 2 0 0 0 1 1 1 1 2
Output
4Zyn!
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];}}}elsenum-=cnt1[cnt];if(num>=cnt2[cnt]){num-=cnt2[cnt];ans+=cnt2[cnt];}elseans+=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;
}