解題區/解題區 - UVa

UVa 10665 - Diatribe against Pigeonholes

contents

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

Problem

包裹放置於架子上時，盡可能讓兩側的總量越重越好，而中間放置輕的物品。

找到一種放置方式，同時字典順序越小越好。

Sample Input

1
2
3
4
5
6
7
8
9
4
5
BDCECDCBCBCDECDABCEDVBCDBCDBCDABCAED#
7
BGFADCEDGFCDEGCFCGDGCXXDAEDACEACEGFAGFCEDGCEDGBCD#
24
AABACDEDFGHMMJNTBNHGTDFACCDLLPPPERRAMMMMKKKKJJJHHHAAAAGGGQQQLLLLPPPAA#
10
PDJFGEDFANGEHIAEJBHJGEDGJGJEINDFJHEIEDGHFFGHDHGFHAJGIE#

Sample Output

1
2
3
4
5
6
7
8
C B A E D
11 8 3 4 9
C D A B F E G
10 9 5 2 5 7 9
A L G D C B E F I O S U V W X N R T Q J K H M P
11 6 5 4 3 2 2 2 0 0 0 0 0 0 0 2 2 2 3 4 4 5 6 6
E H D A B C I F J G
8 7 6 3 1 0 4 6 7 9

Solution

很明顯地可以使用貪心策略，每一次決定方最左或者是最右邊的項目。

由於要維持最小字典順序，放置兩個物品時

  • 如果這兩個重量相同，則字典順序最小的放前面，最大的放後面。
  • 反之，找到挑一個 同一個重量 字典順序小的放前面。
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
#include <stdio.h> 
#include <algorithm>
#include <vector>
using namespace std;
bool cmp1(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second || (a.second == b.second && a.first < b.first);
}
bool cmp2(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second || (a.second == b.second && a.first > b.first);
}
int main() {
    int testcase, N;
    char s[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf ("%d %s", &N, s);
        pair<int, int> cnt[26] = {}, ret[26];
        for (int i = 0; i < N; i++)
            cnt[i].first = i + 'A';
        for (int i = 0; s[i] != '#'; i++) {
            if (s[i] >= 'A' && s[i] <= 'Z')
                cnt[s[i] - 'A'].second ++;
        }
        int l = 0, r = N - 1;
        for (int i = 0; i < N; ) {
            if (i+1 < N) {
                sort(cnt+i, cnt + N, cmp1);
                if (cnt[i].second != cnt[i+1].second) {
                    if (cnt[i].first < cnt[i+1].first) {
                        ret[l++] = cnt[i];
                        sort(cnt+i+1, cnt + N, cmp2);
                        ret[r--] = cnt[i+1];
                    } else {
                        swap(cnt[i], cnt[i+1]);
                        ret[l++] = cnt[i];
                        sort(cnt+i+1, cnt + N, cmp2);
                        ret[r--] = cnt[i+1];
                    }
                } else {
                    sort(cnt+i, cnt + N, cmp1);
                    ret[l++] = cnt[i];
                    sort(cnt+i+1, cnt + N, cmp2);
                    ret[r--] = cnt[i+1];
                }
                i += 2;
            } else {
                ret[l] = cnt[i];
                i++;
            }
        }
        for (int i = 0; i < N; i++)
         	printf("%c%c", ret[i].first, i == N - 1 ? '\n' : ' ');
     	for (int i = 0; i < N; i++)
         	printf("%d%c", ret[i].second, i == N - 1 ? '\n' : ' ');
    }
    return 0;
}