HDU 6669 Game

hdu题面

解题思路

首先我们要选一个起点，这个起点应该在第一个区间内，然后再看第二个区间在左边还是右边以便移动，但转念一想，我们可以把起点直接选在前一堆区间的交集上，于是思路就有了——依次把所有区间取交集，如果没有交集就搞一个新的区间，之后的接着取交集，得到一堆合并出来的区间。然后就在合并的区间上移动就好。

有一个细节要注意。举个例子，如果现在位置在\(3\)，之后的两个目标区间依次是\([6,7]\)、\([9,10]\)，那么我们如果经过两次移动（先1后2）到达第一个区间的左端点\(6\)，下一步就要再移动两次才能到达\(9\)，所以第一步不妨用相同的代价（两次移动）多走点，走到7，那么第二步到\(9\)就只用移动一次就好。

比赛时合并区间写的有问题，WA*7，最后两题惨淡收场……

源代码

#include<cstdio>
#include<algorithm>
int T,n;
struct D{
    int a,b;
}p[1010];
int num;
int l,r;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        num=0;
        scanf("%d%d%d",&n,&l,&r);
        for(int i=1,a,b;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            if(a>r||b<l)
            {
                p[num++]={l,r};
                l=a;
                r=b;
            }
            else
            {
                l=std::max(l,a);
                r=std::min(b,r);
            }
            if(i==n-1) p[num++]={l,r};//比赛时这句话被我写到循环外面去了……
        }
        int pos;
        if(p[0].b<p[1].a) pos=p[0].b;
        else pos=p[0].a;
        long long ans=0;
        for(int i=1;i<num;i++)
        {
            if(pos<p[i].a)//向右走
            {
                int delta=p[i].a-pos;
                pos=p[i].a;
                ans+=delta>>1;
                if(delta&1)
                {
                    ans++;
                    if(i+1<num&&pos+1<=p[i].b&&p[i+1].a>pos) pos++;
                }
            }
            else//向左走
            {
                int delta=pos-p[i].b;
                pos=p[i].b;
                ans+=delta>>1;
                if(delta&1)
                {
                    ans++;
                    if(i+1<num&&pos-1>=p[i].a&&p[i+1].b<pos) pos--;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

HDU 6669 Game

原文：https://www.cnblogs.com/wawcac-blog/p/11372727.html