/
234.cpp
68 lines (55 loc) · 1.61 KB
/
234.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <cstring>
#include <algorithm>
#include <limits.h>
using namespace std;
int atimes[10], aimp[10], na, durations[10], np, missTimes[10], tmp[10], bestOrder[10], tmpSum, curSum;
int d;
void calcMissTimes() {
memset(tmp, 0, sizeof(tmp));
tmpSum = 0;
for (int i = 0; i < na; i++) {
int start = 0, minMiss = 9999999;
for (int j = 0; j < np; j++) {
minMiss = min(minMiss, min(abs(start - atimes[i]), abs(start + durations[j] - atimes[i])));
start += durations[j];
}
tmp[aimp[i]] += minMiss;
tmpSum += minMiss;
}
}
bool tmpSmaller() {
// if (tmpSum < curSum) return true;
// else if (tmpSum > curSum) return false;
for (int i = 0; i < 10; i++)
if (tmp[i] < missTimes[i]) return true;
else if (tmp[i] > missTimes[i]) return false;
return false;
}
void solve() {
do {
calcMissTimes();
if (tmpSmaller()) {
memcpy(missTimes, tmp, sizeof(missTimes));
memcpy(bestOrder, durations, sizeof(durations));
curSum = tmpSum;
}
} while (next_permutation(durations, durations + np));
}
int main() {
while (cin >> np and np) { d++;
curSum = INT_MAX;
memset(missTimes, 0, sizeof(missTimes));
for (int i = 0; i < np; i++) { cin >> durations[i]; }
cin >> na;
for (int i = 0; i < na; i++) { cin >> aimp[i] >> atimes[i]; missTimes[i] = INT_MAX; }
sort(durations, durations + np);
solve();
cout << "Data set " << d << endl;
cout << "Order: ";
for (int i = 0; i < np; i++) { cout << bestOrder[i]; if (i != np - 1) cout << ' '; }
cout << endl;
cout << "Error: " << curSum << endl;
}
return 0;
}