二分查找-CodeForces 812C-Sagheer and Nubian Market

二分查找-CodeForces 812C-Sagheer and Nubian Market

题目链接：C. Sagheer and Nubian Market
思路：

题目大意是有n件纪念品，一共有S元，如果买k件，那第i件纪念品的时间价格truePrice=Price+k*i ，问在S内，最多能买多少件纪念品，如果有多种情况，选总花费最少的。

数据：n and S (1 ≤ n ≤ 10^5 and 1 ≤ S ≤ 10^9) 不出意外暴力会超时，用二分做，合法的化区间就往右走

然后要考虑总花费最小，定义一个优先队列，自定义greater(队头为最小价格），这样指定购买数目内可得最小总价

代码：

include

using namespace std;

define MAX_SIZE 100005

long long n,S,Consum,MinPrice=0,Max_num=0;
long long a[MAX_SIZE];

bool Judge(long long Mid)
{

Consum=0;
priority_queue<long long,vector<long long>,greater<long long> > Price_List;
for(long long i=1;i<=n;i++)
    Price_List.push(a[i]+Mid*i);
for(long long i=0;i<Mid;i++)
{
    Consum+=Price_List.top();
    Price_List.pop();
}
return Consum<=S;   //总花费不大于S

}

int main()
{

cin>>n>>S;
for(long long i=1;i<=n;i++)
    scanf("%lld",&a[i]);
long long Left=1,Right=n,Mid;
while(Left<=Right)
{
    Mid=(Left+Right)/2;
    if(Judge(Mid))  //合法时记录下最大购买及最小总价
    {
        Left=Mid+1;
        MinPrice=Consum;
        Max_num=Mid;
    }
    else
        Right=Mid-1;
}
cout<<Max_num<<" "<<MinPrice<<endl;
return 0;