C++(g++ 7.5.0) 解法, 执行用时: 695ms, 内存消耗: 16052K, 提交时间: 2023-01-05 11:04:26

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

ll limit, n, x, y, sum = 0;

//随从
struct gf {
	ll num, z;
}a[1000010];

bool cmp1(gf a, gf b) {
	return a.z < b.z;
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		cin >> limit >> n >> x >> y;
		for (int i = 1; i <= n; i++) {
			cin >> a[i].z >> a[i].num;
			sum += a[i].num;
		}
		//0攻嘲讽
		if (x == 0)
		{
			cout << 1 << endl;
			continue;
		}
		//按亡语进行排列
		sort(a + 1, a + 1 + n, cmp1);
		ll max = y, min = y;
		//剩余格子数
		ll spare = limit - sum;
		ll sumnow = sum;
		for (int i = 1; i <= n; i++) {
			//血量最大情况：先把所有亡语撞开，让1-1最少
			if (a[i].z == 0) continue;
			max -= a[i].num;
			if (limit >= sumnow + (a[i].z - 1) * a[i].num)
			sumnow += (a[i].z - 1) * a[i].num;
			else 
			sumnow = limit;
		}
		max -= sumnow;
		for (int i = 1; i <= n; i++) {
			if (a[i].z + sum - 1 > limit)
			{
				long long int d = sum + a[i].z - 1 - limit;
				if (a[i].num >= d)
				{
					min = min - d * (limit - sum + 1 + limit - sum + d) / 2 - d;
					min = min - (a[i].num - d) * (a[i].z + 1);
				}
				else
				{
					min = min - a[i].num * (limit - sum + 1 + limit - sum + a[i].num) / 2 - a[i].num;
				}
			}
			else
				//每一种怪的第一个撞开亡语全容纳
				min = min - a[i].num * (a[i].z + 1);
			    sum -= a[i].num;
		}
		cout << max - min + 1 << endl;
	}
}

C++ 解法, 执行用时: 898ms, 内存消耗: 16040K, 提交时间: 2021-11-27 13:36:09

#include<bits/stdc++.h>
using namespace std;
long long limit,T,n,x,y,hit,k,maxd,mind,cnt;
struct S
{
	long long z,num;
}a[1000000];
bool cmp(S x,S y)
{
	return x.z<y.z;
}
int main()
{
	int i;
	cin>>T;
	while(T--)
	{
		k=maxd=mind=cnt=0;
		cin>>limit>>n>>x>>y;
		if(x)
		{
			for(i=0;i<n;i++)
			{
				cin>>a[i].z>>a[i].num; k+=a[i].num; 
				if(a[i].z) mind+=a[i].z*a[i].num;
				else cnt+=a[i].num;
			}
			sort(a,a+n,cmp);
			mind=k+min(limit-cnt,mind); 
			for(i=0;i<n;i++)
	 	    {
				if(k-1+a[i].z<=limit) maxd+=(a[i].z+1)*a[i].num;
				else if(a[i].z+k-a[i].num>limit) maxd+=(2*limit-2*k+a[i].num+3)*a[i].num/2;
				else maxd+=(a[i].z+k-limit)*(limit+a[i].z-k+1)/2+a[i].num+a[i].z*(a[i].num-a[i].z+limit-k);
				k-=a[i].num;
			}
			cout<<maxd-mind+1<<endl;
		}
		else 
		{
			for(i=0;i<n;i++)  cin>>a[i].z>>a[i].num;
            cout<<1<<endl; 
		} 
	}
	return 0;
}