【贪心+二分】codeforces C. Sagheer and Nubian Market

http://codeforces.com/contest/812/problem/C

【题意】

如何花最少的钱买最多的纪念品？首要满足纪念品尽可能多，纪念品数量一样花钱要最少，输出纪念品数量以及最少花费。

纪念品的价钱是这么定义的：,其中a是基价，k是总共要买的纪念品数量，x是纪念品的index。

题目给出各个纪念品的基价a（当然,x也随之确定）

【思路】

二分纪念品数量，判断是否满足题意直接贪心，O(n)算出每个纪念品的价钱，O(nlogn)排序,选出最小的mid个；

二分时间复杂度O(n).

所以总的时间复杂度是O(nlogn^2),1000 00刚好满足

【Accepted】

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <cmath>
 4 #include <vector>
 5 #include <algorithm>
 6 #include <set>
 7 #include <map>
 8 #include <queue>
 9 #include <deque>
10 #include <stack>
11 #include <string>
12 #include <bitset>
13 #include <ctime>
14 #include<algorithm>
15 #include<cstring>
16 using namespace std;
17 const int maxn=1e5+5;
18 struct souv
19 {
20     int base;
21     int x;
22 }a[maxn];
23 int n,S;
24 typedef long long ll;
25 int judge(int mid)
26 {
27     ll b[maxn];
28     for(int i=1;i<=n;i++)
29     {
30         b[i]=(ll)a[i].base+(ll)a[i].x*(ll)mid;
31     }
32     sort(b+1,b+n+1);
33     ll sum=0; 
34     for(int i=1;i<=mid;i++)
35     {
36         sum+=b[i];
37     }
38     if(sum<=(ll)S)
39     {
40         return sum;
41     }
42     return -1;
43     
44 }
45 int main()
46 {
47     while(~scanf("%d%d",&n,&S))
48     {
49         for(int i=1;i<=n;i++)
50         {
51             scanf("%d",&a[i].base);
52             a[i].x=i;
53         }
54         int l=0;
55         int r=n;
56         int res=S;
57         while(l<=r)
58         {
59             int mid=(l+r)>>1;
60             int ans=judge(mid);
61             if(ans!=-1)
62             {
63                 res=ans;
64                 l=mid+1;
65             }
66             else
67             {
68                 r=mid-1;
69             }
70         }
71         cout<<r<<" "<<res<<endl;
72     }
73     return 0;
74  }

二分