首页 > 代码库 > 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 青岛赛区网络赛