（2022牛客多校五）B-Watches(二分)

题目：

样例输入：

4 5
3 4 5 6

样例输出：

1

题意：给定n件商品的价格，如果你选购第k件商品，那么购买第i件物品的花费就是ai+k*i，问m元最多能买多少件（第i件是原序列中的第i个）

分析：我们容易发现的一点是答案具有单调性，我能买k件物品，那么我就一定能买k-1件商品，这是显然的，所以我们就可以对商品进行排序，对于每次二分的k我们都需要按照ai+k*i按照从小到大进行排序，然后从前往后贪心地选取即可，看用m元最多能买多少件商品，如果大于k返回true，否则返回false。

下面是代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
struct node{
	int id,v;
}p[N];
int mid,n,m;
bool cmp(node a,node b)
{
	return a.v+a.id*mid<b.v+b.id*mid;
}
bool check(int k)
{
	long long ans=0;
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=k;i++)
		ans+=p[i].v+1ll*p[i].id*k;
	return ans<=m;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d",&p[i].v),p[i].id=i;
	int l=0,r=n;
	while(l<r)
	{
		mid=l+r+1>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	printf("%d",l);
	return 0;
}