贪心_分类讨论_边界问题_1921_C. Sending Messages

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10;

int q[N];

void solve()
{
   
	int n,f,a,b;
	cin>>n>>f>>a>>b;
	
	for(int i=0;i<n;i++)
		cin>>q[i];
	int l=0;
	int end=0;
	for(int i=0;i<n;i++)
	{
   
		if((q[i]-l)*(long long)a>=b&&f>0&&b<f)
		{
   
			f-=b;
			end++;
		}
		else if(f>0&&(q[i]-l)*(long long)a<f&&(q[i]-l)*(long long)a<b)
		{
   
			f-=(q[i]-l)*(long long)a;
			end++;
		}
		
		l=q[i];
	}
	
	if(end!=n)
		cout<<"NO"<<endl;
	else
		cout<<"YES"<<endl;
}

int main()
{
   
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin>>t;
	
	while(t--)
		solve();
	
	return 0;
}

还是准备实事求是的做一些刷题训练，现在自己的rating是939，所以准备做一些900-1000的题

贪心

该题是一个贪心算法，每一次都是维护最小的消耗值，然后用电量减去最小的消耗值，一直到最后一条信息发送出去，电量需要严格大于0，假设最后一条消息发出去的代价是完全消耗电量，那么不合法

如果用我这种写法，注意else if的条件的使用，尽可能把条件列举全面，不然有些情况其实是没有考虑到的

两个int数据相乘可能会超过数据范围，所以需要强制转换一下

l表示的是左边界