AOJ 1347: Shopping

問題

Shopping | Aizu Online Judge

N個の店が等間隔に一直線に並んでいて、店に行く前に店に行かなければならないという制限がある時、最短で行くにはどのくらい歩けば良いか。

解法

1回しか通らない道と3回通る道があるので、それを個々の店の間について考えてやれば良い。

コード

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();

		boolean[] triple = new boolean[n];
		for (int i = 0; i < m; i++) {
			int c = sc.nextInt();
			int d = sc.nextInt();

			for (int j = c; j < d; j++) {
				triple[j] = true;
			}
		}

		int ans = 0;
		for (int i = 0; i < triple.length; i++) {
			if (triple[i]) {
				ans += 2;
			}
		}

		System.out.println(ans + n + 1);
		sc.close();

	}

}