HDU6669 Game（思维，贪心）

维护区间 \([l,r]\) 为完成前 \(i\) 步使用最少步数后可能落在的区间。

初始时区间 \([l,r]\) 为整个坐标轴。

对于第 \(i\) 个任务区间 \([a,b]\)，如果两区间相离，那么至少需要 \((length + 1) / 2\) 步。

在第 \(i\) 个任务完成后，区间 \([l,r]\) 将先扩大 \(length\)，然后再更新为 \([l,r]\) 和 \([a,b]\) 的交集。

时间复杂度为 \(O(n)\) 。

#include<stdio.h>

#include<stdlib.h>

#include<algorithm>

using namespace std;

const int inf = 1e6;

int t, n;

long long a, b, l, r, dist, ans;

int main()

{

    scanf("%d", &t);

    for(int cas = 1; cas <= t; cas++){

        ans = 0;

        l = 0; r = inf;

        scanf("%d", &n);

        for(int i = 1; i <= n; i++){

            scanf("%lld%lld", &a, &b);

            dist = 0;

            if(a > r){

                dist = (a - r + 1) >> 1;

            }

            if(b < l){

                dist = (l - b + 1) >> 1;

            }

            ans += dist;

            /***l和r实际只需更新一边***/

            l -= dist << 1;

            r += dist << 1;

            l = max(l, a);

            r = min(r, b);

        }

        printf("%lld\n", ans);

    }

    return 0;

}

巴特西

HDU6669 Game（思维，贪心）

最新文章

热门文章