首页 > 代码库 > Problem C Shopping 闭环贪心

Problem C Shopping 闭环贪心

技术分享
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1200;
int fa[maxn];

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n+1; i++) fa[i] = i;
    for(int i = 1; i <= m; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        fa[x] = max(fa[x], y);
    }
    long long ans = n+1;
    int l = 1, r = 1;
    for(int i = 1; i <= n; ){
        r = fa[i];
        int now = i;
        while(now <= r){
            r = max(r, fa[now]);
            now++;
        }
        ans += 2*(r-i);
        i = now;
    }
    printf("%lld\n", ans);
    return 0;
}
View Code

在一条街上有1-n个店,你一开始在0这个位置,你需要访问每个店,并且最后到n+1这个点

然后有m个限制,就给你ci,di

表示你去ci这个店之前,你必须先到di这个点才行

保证di>ci

问你最小距离走多少

 

 

往回走一次,再走过去就好了!!!!

Problem C Shopping 闭环贪心