首页 > 代码库 > HDU 5881 Tea -2016 ICPC 青岛赛区网络赛
HDU 5881 Tea -2016 ICPC 青岛赛区网络赛
题目链接
题意：有一壶水, 体积在 L和 R之间, 有两个杯子, 你要把水倒到两个杯子里面, 使得杯子水体积几乎相同(体积的差值小于等于1), 并且使得壶里剩下水体积不大于1. 你无法测量壶里剩下水的体积, 问最小需要倒水的次数。
题解：考虑倒水的大致过程，L = 0 和 L = 1 的情况应该是等价的，所以不妨设 L > 0。首先向一个杯子倒 L/2 升水，再往另一个杯子倒 L/2+1 升水。接下来就来回往两个杯子里倒 2 升，直到倒空为止。这样就很容易分析出需要倒水的次数。唯一注意的是最后壶里面可以剩下 1 升水，可以省一次倒水的操作。
以上就是官方的题意题解了，下面来总结一下我自己的看法和自己犯的错误。比赛的时候队友把这个题过了，我后来也写了一次没过zzz，比照她的代码写了个生成随机数跑了N组数据比照data1.out和data2.out找到了好多错误样例慢慢调试终于过了TAT。开始的时候考虑的不够周到，理解成来回往两个杯子里倒1升了，后来改对了。这道题我们只需要考虑R-1升水因为可以剩1升，r=0，r=1 输出0，r=2输出1即可。当l>0时，我们可以直接考虑l+2升水，比如l=3,我们考虑5，一个2一个3，先倒个2，另一个就算不足3也没关系因为最少是1是符合题意的，相当于越界到l+2，即我们只需要考虑(r-1)-(l+2)升水，两升两升取，直接除以2如果奇数就再加一次就行了。这里要特别注意l=0的时候只能越到l+1，因为L=0的时候两个杯子拉不开差距只能越到L+1，剩下同理。还有就是要注意当l和R离得很近的时候要特判一下，如果近到一定程度可以直接输出1或者2，负数跑进奇偶性判断那就不对了，当然也可以用max(sum,0)来实现。还要注意if else能输出就直接输出，别最后输出容易max错成别的数。0ms就可以过。
我的代码：
#include <bits/stdc++.h>using namespace std;typedef long long ll;int main(){ ll l,r; while(scanf("%I64d%I64d",&l,&r)!=EOF) { ll ans; if (r<=1) puts("0"); else if(r<=2) puts("1"); else if(l==0) //越到L+1 { ll sum=r-l-2; if(sum<0) ans=1; else if(sum%2==0) ans=sum/2+1; else ans=sum/2+2; printf("%I64d\n",ans); } else //越到L+2 { ll sum=r-l-3; if(sum<0) ans=2; else if(sum%2==0) ans=sum/2+2; else ans=sum/2+3; printf("%I64d\n",ans); } } return 0;}
队友代码：
#include <iostream>#include<cstdio>using namespace std;long long max(long long l,long long r){ if(l<r)return r; return l;}int main(){ long long l,r; while(~scanf("%I64d%I64d",&l,&r)) { if(r>2)printf("%I64d\n",max((r-max(l,1LL))/2+1,2)); else if(r>1)puts("1"); else puts("0"); } return 0;}
HDU 5881 Tea -2016 ICPC 青岛赛区网络赛