首页 > 代码库 > 7-20测试
7-20测试
问题 A: 选择困难症
时间限制: 1 Sec 内存限制: 128 MB提交: 485 解决: 110
[提交][状态][讨论版]
题目描述
又到吃饭时间，Polo 面对饭堂里琳(fei)琅(chang)满(keng)目(die)的各种食品，又陷入了痛苦的抉择中：该是吃手(jiao)打肉饼好呢，还是吃豆(cai)角(chong)肉片好呢？嗯……又不是天秤座怎么会酱紫呢？
具体来说，一顿饭由M 个不同的部分组成(荤菜，素菜，汤，甜品，饮料等等)，Polo 要在每个部分中选一种作为今天的午饭。俗话说的好，永远没有免费的午餐，每种选择都需要有一定的花费。长者常常教导我们，便宜没好货，最便宜的选择估计比较坑爹，可囊中羞涩的Polo 还要把钱省下来给某人买生日礼物，这该怎么办呢？
于是一个折中方案出来了：第K 便宜的组合要花多少钱？这就要靠你了。
输入
第一行两个数M，K，含义如上所述。
接下来M 行，先是一个整数Ai，表示第i 个部分有多少种选择。接下来用空格分开的Ai 个整数表示每种选择的价格。
输出
一行一个整数表示答案。
样例输入
2 22 1 32 2 2
样例输出
3
提示
【样例解释】
最便宜的选择是第一部分选择1 块钱的，第二部分选择2 块的。但由于第二部分里2 块钱有两种不同的选择，所以第二便宜的总花费仍然是3 块。这道题一开始想到了一个方法，可以拿五十分。另f[i]表示从前i种菜品的选择中前k便宜的价钱。f[i]可以只从f[i-1]转来。——如果前i-1种菜品的选择是第k+1优的，则其算上第i种菜品后一定不会进前k便宜。这样枚举一下，时间复杂度O(K^2*M);50分。
#include<iostream>#include<algorithm>#include<cstdio> using namespace std;int f[100005],st[3000005],m,k,num,a[100005];int main(){ scanf("%d %d",&m,&k); for(int i=1;i<=m;i++) { scanf("%d",&num); for(int P=1;P<=num;P++) scanf("%d",&a[P]); sort(a+1,a+1+num); int tot=0; for(int j=1;j<=k&&f[j];j++) for(int w=1;w<=num;w++) { st[++tot]=f[j]+a[w]; } if(i==1) { for(int w=1;w<=num;w++) f[w]=a[w]; } sort(st+1,st+1+tot); if(i!=1) for(int j=1;j<=k;j++) f[j]=st[j; } cout<<f[k]<<endl;}
标程就是上述的暴力加上堆优化。我们只要求前k优的花费，只需要一个贪心就行了。
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<queue>using namespace std;long long n,k,a[500008],b[500008],f[11][500008],tot;long long ans;priority_queue<long long> qu;int main(){ scanf("%lld%lld",&n,&k); ans=0; for(int i=1;i<=n;i++){ scanf("%lld",&f[i][0]); for(int j=1;j<=f[i][0];j++) scanf("%lld",&f[i][j]); sort(f[i]+1,f[i]+1+f[i][0]); } tot=min(k,f[1][0]); for(int i=1;i<=tot;i++) b[i]=f[1][i]; for(int i=2;i<=n;i++){ long long flag=100000000000000; for(int j=1;j<=f[i][0];j++) for(int g=1;g<=tot;g++){ if(b[g]+f[i][j]>flag) break; if(qu.size()<k){ qu.push(b[g]+f[i][j]); if(qu.size()==k) flag=qu.top(); }else{ if(b[g]+f[i][j]<flag){ qu.pop(); qu.push(b[g]+f[i][j]); flag=qu.top(); } } } tot=0; while(!qu.empty()){ b[++tot]=qu.top(); qu.pop(); } for(int i=1;i<=tot/2;i++){ swap(b[i],b[tot-i+1]); } } printf("%lld",b[k]);}
7-20测试
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。