题解 | G-why买外卖

时间复杂度：O(max(T * n, n * log n))

运用了前缀和的知识

using namespace std;
#include<map>

int main()
{
	int T;
	cin >> T;
	int n, i=0,a,b;
	long long m;
	map<long, long> q;   //注意map中默认按键的大小从小到大升序排序，若想调整排序顺序则需放入vector中
	long long ans; 
	while (T--)              //注意在每一组的答案输出后要进行初始化
	{
		cin >> n >> m;
		ans = m;
		for (i=0; i < n; i++)
		{
			cin >> a >> b;
			if (q.count(a))//如果ai存在则优惠叠加
			{
				q[a] += b;
			}
			else q[a] = b;
		}
		auto it1 = q.begin();
		auto it2 = q.begin();
		it2++;
		for (; it2 != q.end(); it1++,it2++)//由于优惠叠加，这里运用了前缀和
		{
			it2->second += it1->second;
		}
		for (it1 = q.begin(); it1 != q.end(); it1++)
		{
			if (m + it1->second >= it1->first)//优惠后的价格最高一定是m
			{
				ans = m + it1->second;
			}

		}
		cout << ans << endl;
		q.clear();
		
	}

	return 0;
}

如有错误欢迎指出