【贪心+二分】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】

 #include <iostream>

 #include <stdio.h>

 #include <cmath>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <string>

 #include <bitset>

 #include <ctime>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int maxn=1e5+;

 struct souv

 {

     int base;

     int x;

 }a[maxn];

 int n,S;

 typedef long long ll;

 int judge(int mid)

 {

     ll b[maxn];

     for(int i=;i<=n;i++)

     {

         b[i]=(ll)a[i].base+(ll)a[i].x*(ll)mid;

     }

     sort(b+,b+n+);

     ll sum=;

     for(int i=;i<=mid;i++)

     {

         sum+=b[i];

     }

     if(sum<=(ll)S)

     {

         return sum;

     }

     return -;

 }

 int main()

 {

     while(~scanf("%d%d",&n,&S))

     {

         for(int i=;i<=n;i++)

         {

             scanf("%d",&a[i].base);

             a[i].x=i;

         }

         int l=;

         int r=n;

         int res=S;

         while(l<=r)

         {

             int mid=(l+r)>>;

             int ans=judge(mid);

             if(ans!=-)

             {

                 res=ans;

                 l=mid+;

             }

             else

             {

                 r=mid-;

             }

         }

         cout<<r<<" "<<res<<endl;

     }

     return ;

  }

二分

巴特西

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

最新文章

热门文章