POJ 2188 - Cow Laundry

http://poj.org/problem?id=2188

概要

N 本の糸が上下に張られており，これを交差が無いようにしたい． 上側か下側の隣接した糸を入れ替える操作しかできないとして，交差が無い形にするために必要な最小の操作回数を答える．

i 行目のインプット a, b は「i 本目の糸が上側の左から a 番目と下側の左から b 番目を結んでいる」という意味． この意味を理解するのに一番時間がかかった…

制約

• 1 <= N <= 1000

解法

POJ 3067 - Japan と同様に大小関係が逆転している組み合わせの数を数えるだけ．

今回は N <= 1000 なので，ナイーブに O( N^2 ) で数えても十分間に合う．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   cin >> N;
 9   vector<pair<int,int> > wires(N);
10   for (int i = 0; i < N; i++) {
11     int a, b;
12     cin >> a >> b;
13     --a;  --b;
14     wires[a].first = wires[b].second = i;
15   }
16 
17   int ans = 0;
18   for (int i = 0; i < N; i++) {
19     for (int j = i+1; j < N; j++) {
20       if ((wires[i].first - wires[j].first) * (wires[i].second - wires[j].second) < 0) {
21         ++ans;
22       }
23     }
24   }
25   cout << ans << endl;
26 
27   return 0;
28 }