Tea
题意
题意有点复杂。给你一壶茶,容量范围为$[L,R]$。之后给你两个杯子。让你从茶壶中往杯子里加茶。结果有以下要求。
- 经过$ans$次加水,$ans$最小
- 两个杯子的茶水量相差不超过$1$
- 茶壶中茶水量最终不超过$1$
题解
贪心。
贪心很好想,就是细节很多。
记录茶杯1为a,茶杯2为b。
我们首先向a添加$L/2+0.5$的茶水,之后茶壶中还剩下的范围为$[L/2-0.5,R-L/2-0.5]$。如果满足要求,那么$ans$就是$1$。
之后我们往b添加$L/2-0.5$的茶水,之后茶壶中剩下的范围为$[0,R-L-2]$。如果满足要求,$ans$就是$2$。
之后我们循环往每个茶杯中加入$2$的水,直到满足要求。
需要注意的是,如果$L=0$的话要特判,还有如果$R<=1$那么就直接满足条件,如果$R<=2$的话只要添加一次。
ac代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| #include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for(int i=(a);i<(n);i++) #define per(i,a,n) for(int i=(n-1);i>=(a);i--) #define fi first #define se second typedef pair <int,int> pII; typedef long long ll; const int INF = 0x3f3f3f3f;
ll l,r; int main(){ #ifdef LOCAL freopen("3.in","r",stdin); #endif std::ios::sync_with_stdio(false); cin.tie(0); while(cin>>l>>r){ if(r<=1) puts("0"); else if(r<=2) puts("1"); else if(l==0) printf("%lld\n",(r-1)/2+1); else { ll temp = r-l-3; temp = max(0ll,temp); ll ans = temp/2; if(ans*2<temp) ans++; printf("%lld\n",ans+2); } }
return 0; }
|