[hdoj5881]Tea

Tea

题意

题意有点复杂。给你一壶茶，容量范围为$[L,R]$。之后给你两个杯子。让你从茶壶中往杯子里加茶。结果有以下要求。

• 经过$ans$次加水,$ans$最小
• 两个杯子的茶水量相差不超过$1$
• 茶壶中茶水量最终不超过$1$

题解

贪心。

贪心很好想，就是细节很多。

记录茶杯1为a,茶杯2为b。

1. 我们首先向a添加$L/2+0.5$的茶水，之后茶壶中还剩下的范围为$[L/2-0.5,R-L/2-0.5]$。如果满足要求，那么$ans$就是$1$。

2. 之后我们往b添加$L/2-0.5$的茶水，之后茶壶中剩下的范围为$[0,R-L-2]$。如果满足要求，$ans$就是$2$。

3. 之后我们循环往每个茶杯中加入$2$的水，直到满足要求。

需要注意的是，如果$L=0$的话要特判，还有如果$R<=1$那么就直接满足条件，如果$R<=2$的话只要添加一次。

ac代码

#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;
//head

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;
}