Algoogle

Algorithm for Programming Contest

ACM-ICPC Tokyo Regional 2014 C Shopping

Category: ICPC Tag: implementation

Shopping

問題概要


0が入り口, n+1が出口の道に1~nの店がある.
dに行ってからcに行きたいという情報がm個来る.
ただしc<d
これらを満たしつつ全ての店を回るのに必要な最小の移動距離を求めよ

解法


与えられる各順番について, その区間はちょうど1回往復する.
つまり被った区間はマージしてしまえばよい.
被覆される区間の長さ*2+n+1
が答え

コード


(C.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int n, m, seq[1024];

int solve()
{
        int ans = n+1;
        for (int i = 0; i <= n; i++)
                if(seq[i]) ans += 2;
        return ans;
}

void input()
{
        cin >> n >> m;
        int c, d;
        for (int i = 0; i < m; i++) {
                cin >> c >> d;
                for (int j = c; j < d; j++) seq[j] = 1;
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments