链接
题意:一开始有k个水量 , 题目要求你在t天保持l~r的水量,每天固定消耗x水量,一天的刚开始你可以选择加y水量或者不加 ,问t天内是否一直能维持。
思路:
分类讨论, 这题突破点在于x,因为x的范围是最小的,在1e6。小trick,把k和r分别减去l,那么可以减去一边讨论,直接看是否小于0就行了,如果x=y,那么如果第一天能不小于0的话就可以一直苟,如果x>y,那么我们每一天必定加每天固定减少x-y,看看能撑到几天,如果x<y,那么我们直接快没的时候加,也就是在[0~x-1]的范围内加,然后用map记录一下每个位置,如果出现了则说明我只需要操作之前一样的操作就能维持这个数那么就break ,这就是剪枝吗,爱了爱了,复杂度 O ( N ) O(N) O(N)
代码:
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
#define int long long
signed main()
{
int k,l,r,t,x,y;
cin>>k>>l>>r>>t>>x>>y;
r-=l;
k-=l;
bool flag=true;
if(k+y>r && k-x<0)
flag=false;
if(x<y)
{
map<int,bool >mp;
mp[k]=true;
int cnt=0;
while(1)
{
t-=k/x;
k%=x;
if(cnt && mp[k])
break;
cnt++;
mp[k]=true;
if(k+y<=r)
k+=y;
else
{
if(t>0)
flag=false;
break;
}
if(t<=0 )
break;
}
if(t>0 && !mp[k])
flag=false;
}
else if(x==y)
{
if(k+y>r && k-x<0)
flag=false;
}
else if(x>y)
{
if(k+y<=r)
k+=y;
k-=x;
t--;
if(k<0)
flag=false;
int tt=x-y;
int tt2=k/tt;
if(tt2<t)
flag=false;
}
if(!flag)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
return 0;
}