Gym 100803C Shopping（贪心）

Shopping

Your friend will enjoy shopping. She will walk through a mall along a straight street, where N individual shops (numbered from 1 to N) are aligned at regular intervals. Each shop has one door and is located at the one side of the street. The distances between the doors of the adjacent shops are the same length, i.e. a unit length. Starting shopping at the entrance of the mall, she visits shops in order to purchase goods. She has to go to the exit of the mall after shopping. She requires some restrictions on visiting order of shops. Each of the restrictions indicates that she shall visit a shop before visiting another shop. For example, when she wants to buy a nice dress before choosing heels, she shall visit a boutique before visiting a shoe store. When the boutique is farther than the shoe store, she must pass the shoe store before visiting the boutique, and go back to the shoe store after visiting the boutique. If only the order of the visiting shops satisfies all the restrictions, she can visit other shops in any order she likes. Write a program to determine the minimum required walking length for her to move from the entrance to the exit. Assume that the position of the door of the shop numbered k is k units far from the entrance, where the position of the exit is N + 1 units far from the entrance.

Input

The input file contains several test cases, each of them as described below. Each case input consists of a set of lines.

N m
c1 d1
.
.
.
cm dm

The first line contains two integers N and m, where N (1 ≤ N ≤ 1000) is the number of shops, and m (0 ≤ m ≤ 500) is the number of restrictions. Each of the next m lines contains two integers ci and di (1 ≤ ci < di ≤ N) indicating the i-th restriction on the visiting order, where she must visit the shop numbered ci after she visits the shop numbered di (i = 1, . . . , m).

There are no pair of j and k that satisfy cj = ck and dj = dk.

Output

For each test case, output the minimum required walking length for her to move from the entrance to the exit. You should omit the length of her walk in the insides of shops.

Sample Input

Sample Output

23 
19 
11

链接

https://vjudge.net/problem/Gym-100803C

题意

一条直线上有n个点，标号从1到n，起点为0，终点为N+1，给定m个限制关系（ci，di），访问ci点前必须先访问di点，每两个点之间是单位距离，求在限制条件下，从起点到终点访问完所有的点的最短距离。

题解

画图模拟一下可知，从起点0到终点的N+1这段距离是必须的，若想距离最短，必须去重。
比如以下样例：
10 3
3 7
8 9
2 5
试模拟一下按部就班的访问，从0开始，先访问5，再访问2，->7->3->9->8->11,最后结束，因为要满足限制条件，会重走一些路，有些重走是不可避免的，比如限制条件8 9,为了先访问9再访问8，必须将8~9这一段走2遍，但是限制条件2 5和3 7则不然，不必要将2~5和3~7都重走2遍，画图显然可知，只需将2~7重走2遍就可同时满足这两个限制条件，也就是说，如果两个限制条件走过的路有交叉（可能是包含）的话，那么取并集即可。

参考自UVaLive6834 Shopping。

代码

Accepted
31 ms
0 KB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 510;

struct node
{
    int l, r;
}a[maxn];

bool cmp(node x, node y)
{
    if (x.r == y.r)
        return x.l > y.l;
    return x.r > y.r;
}

int main()
{
    int n, m, ans, L, R;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        ans = n + 1;
        for (int i = 0; i < m; ++i)
            scanf("%d%d", &a[i].l, &a[i].r);
        sort(a, a + m, cmp); // 排序
        L = a[0].l, R = a[0].r;
        for (int i = 1; i < m; ++i)
        {
            if (a[i].r >= L) // 合并区间
                L = min(a[i].l, L);
            else // 无重合则处理后更新
            {
                ans += (R - L) * 2;
                L = a[i].l, R = a[i].r;
            }
        }
        ans += (R - L) * 2;
        printf("%d\n", ans);
    }
    return 0;
}

The end.
2018-05-19 星期六