[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代码

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