srm 554

发表于   |   分类于   |  

250

Description

给高度为$h_1$的棍子$r_1$个，$h_2$的$r_2$个，轮流放，问最多放出多少种不同的高度

Solution

考虑$h_1$是否等于$h_2$，再讨论即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
struct TheBrickTowerEasyDivOne {
    int find(int r1, int h1, int r2, int h2) {
        if (h1 == h2) {
            return 2 * min(r1, r2) + (r1 == r2 ? 0 : 1);
        }
        else {
            return 2 * min(r1, r2) + (r1 > r2) + min(r1, r2) + (r2 > r1);
        }
    }
};

500

Description

将$n$个数重新排列，使得相邻两个数最大值之和尽量小，同时字典序最小。

Solution

$n$个数算$n-1$的最大值，很显然尽量小的情况是除了最小值所有值都被计算过一次。观察可得，序列应该是先递减再递增的，按字典序排即可。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 50;
vector<pii> s;
vector<int> ans;
bool vis[N];
struct TheBrickTowerMediumDivOne {
    vector <int> find(vector <int> a) {
        int n = a.size();
        ans.pb(0), vis[0] = 1;
        for (int i = 1; i < n; ++i) {
            int p = -1;
            for (int j = 0; j < n; ++j) {
                if (!vis[j] && a[j] <= a[ans[i - 1]]) {
                    p = j;
                    break;
                }
            }
            if (~p) ans.pb(p), vis[p] = 1;
            else break;
        }
        for (int i = 0; i < n; ++i)
            if (!vis[i])    s.pb(mp(a[i], i));
        sort(s.begin(), s.end());
        for (int i = 0; i < s.size(); ++i)  ans.pb(s[i].S);
        return ans;
    }
};