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

6

10 10 10 10 10 9

2 2 2 2 2 3

Sample Output

18

3

Hint

【输入输出样例解释】

　　前3个人去坐汽艇可使快乐程度之和达到最大，每个人的快乐程度均为10-2*2=6，总和是18。

【数据范围】

　　对于30%的数据，n<=20;

　　对于100%的数据，n<=1000。

 

 

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

code：

1 #include
        
          2 #include
         
            3 #include
          
            4 #include
           
             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<
            
             <<'\n'<
            
           
          
         
        

over