第8回日本情報オリンピック 本選 「あみだくじ」 AOJ0540

問題文

頭では解けていたけど実装していなかった問題。
自作アルゴリズムをゴリ押ししたら通った。

• 解法

まず、

サンプルデータの画像で考える。

次のように各横棒に対して二つの整数値を保存しておく。(下のソースではcという配列）

二つの整数値がなにを表しているのかは考えてみてください。

そしたら、横棒を削除していないときの得点がわかります。（int sum;)

そして、それぞれの番号に対応する得点を保存しておきます、（int ans[];)

次に先ほど各横棒に保存していた二つの整数値をすべて見ていきます。

例えば、二つの整数が2と3だった場合、その横棒を消すと2と3の得点が逆になります。

すべての横棒のデータをチェックして消すのに一番いい横棒をみつけてsumからその数を引けば答えが求められる。

計算量はO(M).

C++ ソース

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> P;

int n,m,h,k;
int sum;
int ans[1003];
int yoko[100005];
P c[100005];
int tokuten[1005];
int main(){
	while(1){
	sum = 0;
	priority_queue<P,vector<P>,greater<P> > que;
	scanf("%d%d%d%d",&n,&m,&h,&k);
	if(n+m+h+k == 0)break;
	for(int i = 1;i <= n;i++){
		scanf("%d",&tokuten[i]);
	}
	for(int i = 0;i < m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		que.push(P(b,a));
	}
	for(int i = 1;i <= n;i++){
		yoko[i] = i;
	}
	int co = 0;
	while(que.size()){
		P p = que.top(); que.pop();
		swap(yoko[p.second],yoko[p.second+1]);
		c[co++] = P(yoko[p.second],yoko[p.second+1]);
	}
	for(int i = 1;i <= n;i++){
		ans[yoko[i]] = tokuten[i];
		if(yoko[i] <= k)sum += tokuten[i];
	}
	int hiku = 0;
	for(int i = 0;i < co;i++){
		int a = c[i].first,b = c[i].second;
		if(a > b)swap(a,b);
		if(a <= k && b > k){
			hiku = min(hiku,ans[b]-ans[a]);
		}
	}
	printf("%d\n",sum+hiku);
	}
	return 0;
}