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;
}