11.04T1 枚举

4485 -- 【NOIP2015-4】旅行

Description

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

Input

　　第1行是一个整数n，表示OIer的人数；
　　第2行有n个整数，第i个整数表示第i个人单独坐船的快乐程度Ci（1<=Ci<=10000）；
　　第3行有n个整数，第i个整数表示每多1人，第i个人快乐程度的下降值Di（1<=Di<=10）。

Output

　　第1行一个整数，是最大的快乐程度之和；
　　第2 行一个整数，是最大的快乐程度之和所对应的汽艇上的人数（若有多种方案，则输出人数最多的）。

Sample Input

10 10 10 10 10 9

2 2 2 2 2 3

Sample Output

Hint

【输入输出样例解释】
　　前3个人去坐汽艇可使快乐程度之和达到最大，每个人的快乐程度均为10-2*2=6，总和是18。
【数据范围】
　　对于30%的数据，n<=20;
　　对于100%的数据，n<=1000。

很容易想到 2n 的算法。直接枚举每个人是否在船上,计算取最大值，可以拿到 30%的分数。很明显，直接枚举是没有必要的。我们可以枚举人数 K，然后算出在这种情况下每个人的快乐程度。然后贪心地取前 K 大的数，这样就得到了 n2 logn 的算法。

code：

 1 #include<iostream>
 2 #include<algorithm> 
 3 #include<cstdio>
 4 #include<cstring>
 5 #define N 100006 
 6 using namespace std;
 7 struct node{
 8     int c,d;
 9 }e[N];
10 int sum[N],val[N];
11 bool cmp(int a,int b){
12     return a>b;
13 }
14 int main(){
15     int n;
16     cin>>n;
17     for(int i=1;i<=n;i++)cin>>e[i].c;
18     for(int i=1;i<=n;i++)cin>>e[i].d;
19     int Ans=0,ID;
20     for(int i=1;i<=n;i++){
21         memset(val,0,sizeof val);
22         for(int j=1;j<=n;j++){
23             val[j]=e[j].c-(i-1)*e[j].d;
24         }
25         sort(val+1,val+n+1,cmp);
26         int now=0;
27         for(int j=1;j<=i;j++)now+=val[j];
28         if(now>Ans){
29             Ans=now;
30             ID=i;
31         }
32         else if(now==Ans){
33             ID=i;
34         }
35     }
36     cout<<Ans<<'
'<<ID;
37     return 0;
38 }

over