UVA 11269 - Setting Problems（貪心）

Problem J
Setting Problems

Input: Standard Input

Output: Standard Output

As you see, setting problems for a programming contest is a tough job. There are so many things to do like creating problems, solutions, data files, verification of problem statements, writing alternate judge solutions etc. etc. Given the responsibility of creating the problemset for ‘If you can not crash judges by solutions, crash contestants by problems’ programming contest, Sultan & GolapiBaba have realized that to the backbone. Finally they agree that they will set N problems for the contest. For each of the problems, first Sultan will create the problem statement, solution & i/o data. After he finishes his work, GolapiBaba does the verification & alternate solution writing part for that particular problem. Each of them needs a particular amount of time to complete their tasks for a certain problem. Also, none of them works on more than one problem at a time. Note that, GolapiBaba can start working on a problem immediately after Sultan finishes that problem or he may wish to start that problem later.

You will be given the times that Sultan & GolapiBaba requires to complete their respective tasks for every single problem. Determine the minimum possible time required to complete the whole problemset.

Input

There are around 50 test cases. Each test case starts with a single integer N (1<=N<=20), the number of problems in the contest. The next line contains N integers S_i (1<=S_i<=100, 1<=i<=N) where Si denotes the time required for Sultan to complete his tasks for problem i. The next line has N more integers G_i (1<=G_i<=100, 1<=i<=N) where G_i denotes the time required for Golapibaba to complete his tasks on problem i.

Output

For each test case, print the minimum time required to complete the problemset.

Sample Input

Sample Output

3

8 1 6

1 6 3

3

4 5 6

1 1 6

16

16

思路：貪心，對於兩個任務，只要比較誰先做花的時間少即可。時間分別為(g1 - s2 < 0 ? 0 : g1 - s2) + g2 和(g2 - s1 < 0 ? 0 : g2 - s1) + g1; 小的優先完成。

代碼：

#include 
#include 
#include 
using namespace std;
const int N = 105;

int n;
struct Work {
	int s, g;
} w[N];

bool cmp(Work a, Work b) {
	return (a.g - b.s < 0 ? 0 : a.g - b.s) + b.g < (b.g - a.s < 0 ? 0 : b.g - a.s) + a.g;
}

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

int solve() {
	sort(w, w + n, cmp);
	int have = 0, time = 0;
	for (int i = 0; i < n; i++) {
		have -= w[i].s;
		if (have < 0) have = 0;
		time += w[i].s;
		have += w[i].g;
	}
	return time + have;
}

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