【贪心】【枚举】【重庆市NOIP模拟赛】旅行

题目描述

Mr_H 旗下的 n 个 OIer 坐船外出旅行&＃xff01;
但是他们只有一艘船&＃xff0c;虽然船能装下全部的 Oier&＃xff0c;但太拥挤将会影响众 OIer 的心情&＃xff0c;所以 Mr_H 决定选择一部分 Oier 去。我们假设&＃xff0c;每个人单独坐船的快乐程度是 Ci&＃xff0c;而船上每多一个人&＃xff0c;他的快乐程度会减去 Di。
现在你的任务是帮助 Mr_H 计算&＃xff0c;选择那些人&＃xff0c;才能使船上所有人的快乐程度之和达到最大。

输入

第1行是一个整数 n&＃xff0c;表示 OIer 的人数&＃xff1b;
第2行有 n 个整数&＃xff0c;第 i 个整数表示第 i 个人人单独坐船的快乐程度 Ci&＃xff08;1<&＃61;Ci<&＃61;10000&＃xff09;&＃xff1b;
第3行有 n 个整数&＃xff0c;第 i 个整数表示每多 1 人&＃xff0c;第 i 个人快乐程度的下降值 Di&＃xff08;1<&＃61;Di<&＃61;10&＃xff09;。

输出

第 1 行一个整数&＃xff0c;是最大的快乐程度之和&＃xff1b;
第 2 行一个整数&＃xff0c;是最大的快乐程度之和所对应的汽艇上的人数&＃xff08;若有多种方案&＃xff0c;则输出人数最多的&＃xff09;。

样例输入

6
10 10 10 10 10 9
2 2 2 2 2 3

样例输出

18
3

提示

前 3 个人去坐汽艇可使快乐程度之和达到最大&＃xff0c;每个人的快乐程度均为 10-2*2&＃61;6&＃xff0c;总和是 18。
对于 30%的数据&＃xff0c;n<&＃61;20;
对于 100%的数据&＃xff0c;n<&＃61;1000。

分析

这道题我考试时第一次想的是动态规划&＃xff0c;但是我半天都没有写状态转移方程&＃xff0c;然后就放弃了。。。做下一道题去了。。。后来我回过头来想这道题&＃xff0c;发现可以用贪心&＃43;枚举的方法来做。
通过枚举人数t来讲目前的快乐值排序&＃xff0c;选取前t个数求和&＃xff0c;最大的和就是答案了。然而我在考试的时候担心程序超时&＃xff0c;就记录了一下时间&＃xff0c;发现最慢都只是78毫秒&＃xff0c;于是就AC了。时间复杂度O(n2logn)
小伙伴如果要测试程序时间&＃xff0c;就要在编译器选项加上-Ddebug。

源代码

#include
#include
#include
#include
#include
using namespace std;
int n,t,ans&＃61;-0x3f3f3f3f,ansp;
struct node{int c,d;}k[1001];
bool cmp(node x,node y){return x.c-x.d*(t-1)>y.c-y.d*(t-1);}//按照现在的快乐值排序
int main()
{scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d",&k[i].c);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d",&k[i].d);#ifdef debugdouble a&＃61;clock();//记录起始时间#endiffor(t&＃61;1;t<&＃61;n;t&＃43;&＃43;){sort(k&＃43;1,k&＃43;n&＃43;1,cmp);//排序int tmp&＃61;0;for(int i&＃61;1;i<&＃61;t;i&＃43;&＃43;)//求前t个人的快乐值的和tmp&＃43;&＃61;k[i].c-k[i].d*(t-1);if(tmp>&＃61;ans){ans&＃61;tmp;ansp&＃61;t;}//记录最大的快乐值的和}printf("%d\n%d",ans,ansp);#ifdef debugdouble b&＃61;clock();printf("\n\nn&＃61;%d\ntime:%.lf ms\n&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;\n\n",n,b-a);//输出程序所用时间#endif
}