本文主要是介绍二分查找-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<iostream>
#include<queue>
#include<vector>
#include<cstdio>
#include<algorithm>
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;}elseRight=Mid-1;}cout<<Max_num<<" "<<MinPrice<<endl;return 0;
}
这篇关于二分查找-CodeForces 812C-Sagheer and Nubian Market的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
