HDU 6669 Game（模拟）

淩亂°似流年 2021-10-12 18:40 242阅读 0赞

## 题意：给出n个区间，初始位置可选，依次到达相应的区间，每次可以移动一格或两格，求最小步数。 ##

## 分析：依次将所有区间取交集，然后就变成了一些不重合的区间，第一次可以选择区间的左端点或者右端点，取最大值，贪心模拟就好了，注意如果连续三个区间递增或者递减、间隔步数为奇数并且区间长度大于0，就可以多走一步，代码细节要注意。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N=1e6+5;
    int t,n,m,a[N],b[N];
    vector<pair<int,int> > p;
    
    ll gao(int x) {
        ll ans(0);
        for(int i=1;i<p.size();i++) {
            if(p[i].first>x) {
                ans += (p[i].first-x+1)/2;
                if(i<p.size()-1) {
                    if((p[i].first-x)%2) {
                        if(p[i+1].first>p[i].second && p[i].second-p[i].first>0 ) x=p[i].first+1;
                        else x=p[i].first;
                    }else x=p[i].first;
                }else x=p[i].first;
            }else {
                ans += (x-p[i].second+1)/2;
                if(i<p.size()-1) {
                    if((x-p[i].second)%2)
                        if(p[i].first>p[i+1].second && p[i].second-p[i].first>0 )
                            x=p[i].second-1;
                        else x=p[i].second;
                    else x=p[i].second;
                }else x=p[i].second;
            }
        }
        return ans;
    }
    
    int main() {
        scanf("%d",&t);
        while(t--) {
            p.clear();
            scanf("%d",&n);
            scanf("%d%d",&a[1],&b[1]);
            int l=a[1],r=b[1];
            for(int i=2;i<=n;i++) {
                scanf("%d%d",&a[i],&b[i]);
                if(a[i]<=r && b[i]>=l) {
                    l=max(l,a[i]),r=min(r,b[i]);
                }else {
                    p.push_back({l,r});
                    l=a[i],r=b[i];
                }
            }
            p.push_back({l,r});
            ll ans=2e18;
            ans=min(ans,gao(p[0].first));
            ans=min(ans,gao(p[0].second));
            printf("%I64d\n",ans);
        }
        return 0;
    }
    /*
    3
    4
    4 4
    5 10
    3 5
    8 10
    */