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