题意:有一壶水, 体积在 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<=) puts("");
else if(r<=) puts("");
else if(l==) //越到L+1
{
ll sum=r-l-;
if(sum<)
ans=;
else if(sum%==)
ans=sum/+;
else
ans=sum/+;
printf("%I64d\n",ans);
}
else //越到L+2
{
ll sum=r-l-;
if(sum<)
ans=;
else if(sum%==)
ans=sum/+;
else
ans=sum/+;
printf("%I64d\n",ans);
}
}
return ;
}
队友代码:
#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>)printf("%I64d\n",max((r-max(l,1LL))/+,));
else if(r>)puts("");
else puts(""); } return ;
}