评分

Posted on In

题目大意：你参加了一次比赛，共有 𝑛（奇数）个评委给你打分， 编号为 1 到 𝑛 。你最终的得分通过如下方式得到：评委们按编号排成一排，每次取出前三名评委，留下其中评分的中位数并将其加入队尾，直到只剩最后一名评委，该评委的评分就 是你最终的得分。现在你知道了所有评委的评分和部分评委的编号，你想要知道，对于剩余评委所有可能的编号情况中，你的得分最高能达到多少。

我们正着搞貌似有点麻烦，所以考虑二分，转化成一个判定型问题（其实考试的时候我想到二分了，但是没有细想，也没有时间，因为我觉得这题暴力分拿满就行了，并且搜索题还没写，略微有点慌）

我们考虑‘01规划’，把大于mid的都判定为1，小与mid的判定为0，

由题可知，我们每次取出三个数，我们希望结果是大于等于mid的，所以我们就要这三个数里面有两个1

然后考虑每个数如何变为1，设\(f(x)\)表示表示x这个数字变成1需要多少个1

显然：

\(f(mid^+)=0​\)大于mid的数，不需要变化，所以为0

\(f(mid^-)=inf​\)小于mid的数字，变不成，所以为inf

\(f(?)=1​\)未知大小，显然可以一次变成

其实代码在执行的时候，会不停的判定，许多不合法的情况都会给false掉

注意在二分的时候，我们是找，“在某一个区间范围内的最大值”，所以固定的格式要记住

代码如下：

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 66, inf = 214748364;

inline int read()
{
    int s(0), w(1);
    char ch = getchar();
    while (ch < '0' || ch > '9'){if (ch == '-') w = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline void put(int x)
{
    if (! x) putchar('0');
    if (x < 0) putchar('-'), x = -x;
    int num(0); char c[66];
    while (x) c[++ num] = x % 10 + 48, x /= 10;
    while (num) putchar(c[num --]);
    return (void)(putchar('\n'));
}

queue<int>q;
int n, m, res;
int num[N], num2[N], val[N];

inline int pd(int x)
{
    int i, lim(0);
    for (i = 1; i <= n - m; ++ i) if (num2[i] >= x) ++ lim;
    for (i = 1; i <= n; ++ i) q.push(num[i] ? (num[i] >= x ? 0 : inf) : 1);
    while (! q.empty())
    {
        int a, b, c;
        a = q.front(); q.pop();
        if (q.empty()) return a <= lim;
        b = q.front(); q.pop();	
        c = q.front(); q.pop();
        q.push(min(inf, min(a + b, min(a + c, b + c))));
    } 
}

signed main()
{
    int i, j, k; 

    n = read(), m = read();

    for (i = 1; i <= m; ++ i)
    {
        j = read(), k = read();
        num[k] = val[i] = j;
    }
    for (i = 1; i <= n - m; ++ i) val[i + m] = num2[i] = read();
    sort(val + 1, val + n + 1);

    int l = 1, r = n;
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        if (pd(val[mid])) l = mid;
        else r = mid - 1;
    }

    put(val[l]);
    return 0;
}