我的第一篇题解（辣鸡题解）洛谷 P1230 智力大冲浪
题目描述
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：
首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!
输入输出格式
输入格式：
输入文件riddle.in，共4行。
第1行为m，表示一开始奖励给每位参赛者的钱；
第2行为n，表示有n个小游戏；
第3行有n个数，分别表示游戏1到n的规定完成期限；
第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。
输出格式：
输出文件riddle.out，仅1行。表示小伟能赢取最多的钱。
输入输出样例
输入样例1
10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
输出样例1
9950
下面来看思路啦：
诶哟，刚看到这题时，还觉得挺简单的：哇，不就是个贪心加排序吗？结果，做错啦TAT！
本题思路：
因为要让小伟获得的奖金最多，就应该从扣款数多的小游戏开始玩儿~所以呢，a表示游戏规定完成的期限，b表示不能在规定期限前完成的扣款数，c表示这个小游戏有没有玩过。我们可以把b数组从大到小排一个序，然后枚举b[i]，能完成这个游戏就完成这个游戏，这酱紫就可以就可以让小伟扣掉的奖金最少啦~
下面根据我的受到的教训，总结一下这题需要注意的：
一、可以使用结构体（这是最好），可惜懒惰加奇葩的我就是不愿意，非要用数组（还要手写快排QAQ）
二、（dalao可以略过，细心的童鞋也可以略过）纯属小粗心，输入的时候一定要分两个for循环来做啊，不要像我一样，一开始只用了一个循环TAT，找了10多分钟，才发现错误555~
下面贴上本蒟蒻的代码：
无注释版：
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int ans,n; int a[1001],b[1001]; bool flag[1001]; void quicksort(int l,int r) { int i,j,m; i=l; j=r; m=b[(i+j)/2]; do { while (b[i]>m) i++; while (b[j]<m) j--; if (i<=j) { swap(a[i],a[j]); swap(b[i],b[j]); i++; j--; } } while (i<=j); if (i<r) quicksort(i,r); if (j>l) quicksort(l,j); } int main() { cin>>ans>>n; for (int i=1;i<=n;i++) cin>>a[i]; for (int j=1;j<=n;j++) cin>>b[j]; quicksort(1,n); for (int i=1;i<=n;i++) { for (int j=a[i];j>=1;j--) { if (flag[j]==0) { flag[j]=1; b[i]=0; break; } } } for (int i=1;i<=n;i++) ans=ans-b[i]; cout<<ans<<endl; return 0; }
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int ans,n; int a[1001],b[1001]; bool flag[1001];//判断该时段有没有玩过游戏 void quicksort(int l,int r)//快速排序 { int i,j,m; i=l; j=r; m=b[(i+j)/2]; do { while (b[i]>m) i++; while (b[j]<m) j--; if (i<=j) { swap(a[i],a[j]); swap(b[i],b[j]); i++; j--; } } while (i<=j); if (i<r) quicksort(i,r); if (j>l) quicksort(l,j); } int main() { cin>>ans>>n; for (int i=1;i<=n;i++) cin>>a[i]; for (int j=1;j<=n;j++) cin>>b[j]; quicksort(1,n);//从大到小排序 for (int i=1;i<=n;i++)//枚举b[i] { for (int j=a[i];j>=1;j--) { if (flag[j]==0)//如果没有玩过 { flag[j]=1; b[i]=0; break; } } } for (int i=1;i<=n;i++) ans=ans-b[i];//计算奖金 cout<<ans<<endl; return 0; }
希望各位能在里面学到些东西~（然而是不可能的QWQ）
作者：暄妍
我的博客：http://www.cnblogs.com/zbyrainbow/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。