uva 11269 - Setting Problems(相鄰交換法)

題目鏈接：uva 11269 - Setting Problems

題目大意：有n個任務，每個任務分為兩部分s和w，分別有兩個人處理，只有si做完才能做wi，問最少花費多少時間。

解題思路：貪心， 相鄰交換法，拿出相鄰的兩個人進行比較a在前的時間ta = a.s + max(a.g,b.s) + b.g;b在前的時間

tb= b.s + max(b.g, a.s) + a.g，時間少得放前面。

#include 
#include 

using namespace std;

const int N = 105;

struct state {
	int s, g;
}sta[N];
int n;

bool cmp(const state& a, const state& b) {
	return a.s + max(a.g, b.s) + b.g < b.s + max(b.g, a.s) + a.g;
}

void init() {
	for (int i = 0; i < n; i++) scanf("%d", &sta[i].s);
	for (int i = 0; i < n; i++) scanf("%d", &sta[i].g);
	sort(sta, sta + n, cmp);
}

int solve() {
	int S = 0, G = 0;
	for (int i = 0; i < n; i++) {
		S += sta[i].s;
		if (S > G) G = S + sta[i].g;
		else G += sta[i].g;
	}
	return G;
}

int main() {
	while (scanf("%d", &n) == 1) {
		init();
		printf("%d\n", solve());
	}
	return 0;
}