1. 首页
2. 水题
3. 本页

HDU 5881 Tea (思维)

题目链接：点我~~

题意：有一壶水, 体积在 L和 R之间, 有两个杯子, 你要把水倒到两个杯子里面, 使得杯子水体积几乎相同(体积的差值小于等于1), 并且使得壶里剩下水体积不大于1. 你无法测量壶里剩下水的体积, 问最小需要倒水的次数。

思路：考虑倒水的大致过程，$L=0$ 和 $L=1$ 的情况应该是等价的，所以不妨设$L>0$。首先向一个杯子倒L/2升水，再往另一个杯子倒L/2+1升水。接下来就来回往两个杯子里倒 2 升，直到倒空为止。这样就很容易分析出需要倒水的次数。唯一注意的是最后壶里面可以剩下 1 升水，可以省一次倒水的操作。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN = 100100;

int main()
{
    LL l,r;
    while(cin>>l>>r)
    {
        if(r<=1)
        {
            puts("0");
            continue;
        }
        if(r<=2)
        {
            puts("1");
            continue;
        }
        cout<<max((LL)2,(r-(l==0?1:l))/2+1)<<endl;
    }
    return 0;
}