解題區/解題區 - UVa

UVa 12904 - Load Balancing

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給定一些學生的成績，希望建造一個分級制度，使得每一級的人數差距越少越好。

分級制度化分成 A, B, C, D 四級，每一級都是一個連續區間，假設現在有 N 個人，期望能將每一堆分成 N/4 個人，把每一堆人數與期望的 N/4 的差總和越小越好。

輸出字典順序最小的劃分方式。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
8
0
40
41
80
85
120
150
155
9
0
40
41
80
85
120
121
150
155

Sample Output

1
2
Case 1: 40 80 120
Case 2: 40 80 120

Solution

如何直接窮舉劃分線，想必也要消耗 O(160^3) 的時間。這花費太昂貴。

發現到每一個人的分數並不高，落在 0 - 160 之間的整數，那麼先統計每個分數有多少人。

接著考慮 dp[i][j] 前 i 個分級制度，劃分線為 j 的最小差總和。接著加入下一級，得到

1
dp[i+1][k+1] = min(dp[i+1][k+1], fabs(peopleCount[j, k] - avg) + dp[i][j]);

因此需要 O(4 * 160 * 160) 來完成。考慮輸出最小字典順序的劃分方式，一樣採用 dp 的思路，逆推回去查看是否能得到目標的最佳解，之後再順著被標記的路線走即可。

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
#define MAXV 165
#define eps 1e-6
int main() {
    int testcase, n, x;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int A[MAXV] = {};
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            A[x]++;
        }
        for (int i = 1; i < MAXV; i++)
            A[i] += A[i-1];
        double dp[5][MAXV];
        int used[5][MAXV] = {};
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < MAXV; j++) {
                dp[i][j] = 1e+30;
            }
        }
        dp[0][0] = 0;
        double avg = n/4.0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < MAXV; j++) {
                if (dp[i][j] == 1e+30)
                    continue;
                for (int k = j; k < MAXV; k++) {
                    int cnt = A[k] - (j ? A[j-1] : 0);
                    dp[i+1][k+1] = min(dp[i+1][k+1], fabs(cnt - avg) + dp[i][j]);
                }
            }
        }
        used[4][MAXV - 1] = 1;
        for (int i = 3; i >= 0; i--) {
            for (int j = 0; j < MAXV; j++) {
                if (dp[i][j] == 1e+30)
                    continue;
                for (int k = j; k < MAXV; k++) {
                    int cnt = A[k] - (j ? A[j-1] : 0);
                    if (fabs(fabs(cnt - avg) + dp[i][j] - dp[i+1][k+1]) < eps)
                        used[i][j] |= used[i+1][k+1];
                }
            }
        }
        
        printf("Case %d:", ++cases);
        
        int pos = 0;
        for (int i = 0; i < 3; i++) {
            for (int k = pos; k < MAXV; k++) {
                int cnt = A[k] - (pos ? A[pos-1] : 0);
                if (fabs(fabs(cnt - avg) + dp[i][pos] - dp[i+1][k+1]) < eps && used[i+1][k+1]) {
                    printf(" %d", k);
                    pos = k+1;
                    break;
                }
            }
        }
        puts("");
    }
    return 0;
}
/*
2
8
0
40
41
80
85
120
150
155
9
0
40
41
80
85
120
121
150
155
Case 1: 40 80 120
Case 2: 40 80 120
*/