srm 548

发表于   |   分类于   |  

250

Description

有$N(N\le 50)$个数，每个数的可变范围是$[max(N-X,1),N+X]$。让这个数列严格递增的最小$X$是多少？

Solution

显然可以二分答案，然后二分一个$x$后，我们可以贪心判断，使得前面的数尽量小给后面数更大的变化空间即可

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
35
36
37
38
39
40
41
#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 = 55;
bool check(int x, vector<int> h) {
    int n = h.size();
    for (int i = 0; i < n; ++i) {
        if (!i) {
            if (h[i] - x >= 1)  h[i] -= x;
            else h[i] = 1;
        }
        else {
            if (h[i] + x > h[i - 1]) {
                int t = h[i - 1] + 1;
                h[i] = max(t, h[i] - x);
            }
            else return 0;
        }
    }
    return 1;
}
struct KingdomAndTrees {
    int minLevel(vector <int> heights) {
        int l = 0, r = 1e9;
        int ans = -1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (check(mid, heights)) {
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        return ans;
    }
};

450

Description

有两个$N<50$个面的骰子，每个面的数字是$1\sim X$的唯一某个数。第一个骰子有些面是$0$。现在两个骰子同时投掷，请你把第一个骰子某些为$0$的面写上一些唯一的$1\sim X$的数字，让第一个骰子的胜率尽可能接近$0.5$。

Solution

其实就是考虑将一些数插入一些空里，是否能赢得$k$次，容易想到$dp$，$dp[i][j][k]$表示$前i个数放入j个空能否赢k次$。不妨对第二个数组排序，依次处理即可。

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
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>//dp
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 = 55;
bool dp[N][N * N];
struct KingdomAndDice {
    double newFairness(vector <int> firstDie, vector <int> secondDie, int X) {
        int n = firstDie.size();
        int now = 0, nd = 0;
        sort(secondDie.begin(), secondDie.end());
        for (int i = 0; i < n; ++i) {
            nd += firstDie[i] == 0;
            for (int j = 0; j < n; ++j)
                if (firstDie[i] > secondDie[j]) ++now;
        }
        secondDie.pb(X + 1);
        for (int i = 0; i <= nd; ++i)   dp[i][now] = 1;
        for (int i = 0; i < n; ++i) {
            int l = secondDie[i] + 1;
            int r = secondDie[i + 1] - 1;
            int cnt = r - l + 1;
            for (int j = 0; j < n; ++j)
                if (firstDie[j] >= l && firstDie[j] <= r)   --cnt;
            cnt = min(cnt, nd);
            for (int j = 0; j < cnt; ++j)
                for (int k = nd - 1; k >= 0; --k)
                    for (int p = 0; p <= n * n; ++p)
                        if (dp[k][p] && p + i + 1 <= n * n) dp[k + 1][p + i + 1] = 1;
        }
        double ans = now;
        double mn = 1000000;
        for (int k = 0; k <= n * n; ++k)
            for (int j = 0; j <= nd; ++j)   
                if (dp[j][k] && abs(n * n - k * 2) < mn)    ans = k, mn = abs(n * n - k * 2);
        return ans / n / n;
    }
};