AOJ 0540 あみだくじ
解法
あみだくじにおいて、ある横棒をたどる回数はちょうど2回だから、その横棒を取り去ると2つの縦は交換されない。
つまりa,bがそれぞれc,dにたどり着いている、とすると、a,bがとおる横棒を一つ取り除けば、a,bはそれぞれd,cにたどり着くことになる。
よってすべての横棒について、取り除いた場合どうなるかを調べればよい。
#include <cstdio> #include <algorithm> #include <vector> #define fst first #define snd second using namespace std; const int MAX_N = 1000, MAX_M = 100000; typedef pair<int, int> P; typedef pair<P, P> PP; int n, m, h, k, point[MAX_N]; vector<PP> line; int main(){ while(scanf("%d %d %d %d", &n, &m, &h, &k), n != 0){ line.clear(); for(int i = 0; i < n; i++) scanf("%d", point + i); for(int i = 0; i < m; i++){ int a, b; scanf("%d %d", &a, &b); a--; line.push_back(PP(P(b, a), P(-1,-1))); } sort(line.begin(), line.end()); int v[n]; for(int i = 0; i < n; i++) v[i] = i; for(int i = 0; i < m; i++){ int idx = line[i].fst.snd; line[i].snd.fst = v[idx]; line[i].snd.snd = v[idx + 1]; int t = v[idx]; v[idx] = v[idx + 1]; v[idx + 1] = t; } int sum = 0; int v_rev[n]; for(int i = 0; i < n; i++){ v_rev[v[i]] = i; if(v[i] < k) sum += point[i]; } int ans = sum; for(int i = 0; i < m; i++){ int a, b; a = line[i].snd.fst; b = line[i].snd.snd; if(a > b) swap(a, b); if(a < k && k <= b) ans = min(ans, sum - point[v_rev[a]] + point[v_rev[b]]); } printf("%d\n", ans); } return 0; }