F1 & F2. Microtransactions (easy version) + （hard version） 二分，贪心

easy传送门
hard传送门
参考了：https://blog.csdn.net/hzf0701/article/details/107966085

这题我们二分天数来做，问题就转换成了给定天数，判断能不能达到要求。
这里思考一下，如果在不同的天数有着相同的折扣，那我肯定选择后面的天数进行购买，因为那个时候钱更多，那么我们就可以从后往前开始判断，碰到折扣就全买了

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define endl "\n";
#define ll long long
#define inf 0x3f3f3f3f
const int N = 2e5 + 5;
int a[N];
int b[N];
vector<int>v[2*N]; 
bool check(int n, int d, int sum)
{
	if (d < sum) return false;
	int mm = d;
	int res = 0;
	for (int i = 1; i <= n; i++)
	{
		b[i] = a[i];
	} 
	for (int i = d; i >= 1; i--)
	{
		if (!v[i].empty() && mm)
		{
			for (int j = 0; j < v[i].size(); j++)
			{
				if (b[v[i][j]])
				{
					int temp = min(mm, b[v[i][j]]);
					mm -= temp;
					sum -= temp;
					b[v[i][j]] -=temp;
				}

			}
		}
		if (mm == i) mm--, res++;  //这里要写在后面哦，写在前面第一天的钱可能没有加到
	}
	if (res / 2 >= sum) return 1; //折扣买完了，接下来的钱全部用来买不折扣的
	else return 0;
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i], sum += a[i]; //记录交易的总数量
	}
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		v[a].push_back(b); 
	}
	int l = sum, r = 2 * sum; // 最少天数是sum天，做多是2*sum天，在这区间中做二分
	while (l < r)
	{
		int mid = l + r >> 1;
		if (check(n, mid, sum)) r = mid;
		else l = mid + 1;
	}
	cout << l << endl;
	return 0;
}