HDU 7029. Median

发表于 分类于

链接

https://acm.hdu.edu.cn/showproblem.php?pid=7029

题意

有 $n$ 个不同的数为 $1 \sim n$，将这 $n$ 个数分为 $m$ 个集合，问是否存在一种构造使每个集合的中位数为给出的数。

思路

我们将给出的中位数标记，那么 $1\sim n$ 能够分成好多段连续的没有被标记的数。

易发现可以在两段中各取相同个数的数抵消。

那么可以分为两种情况：

  • 当最长段小于等于其余段之和，一定能全部抵消或者只剩下一个数，不妨让最后一段剩下一个数，那么最终一定能塞入一个中位数小于这个数的集合中，所以一定成立；
  • 当最长段大于其余段之和，最终一定会在最长段中剩下一些数，如果中位数小于当前段的集合个数大于等于剩下的数的个数，那么成立。

代码

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
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
// head
const int N=1e5+5;
bool st[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin>>T;
    while(T--) {
        int n,m;cin>>n>>m;
        memset(st,false,sizeof st);
        for(int i=1;i<=m;i++) {
            int x;cin>>x;
            st[x]=true;
        }
        int cnt=0,len=0;
        PII mx={0,0};
        for(int i=1;i<=n;i++) {
            if(!st[i]) ++len;
            else {
                if(len>mx.FI) mx={len,cnt};
                else if(len==mx.FI) mx.SE=cnt;
                ++cnt;
                len=0;
            }
        }
        if(len>mx.FI) mx={len,cnt};
        else if(len==mx.FI) mx.SE=cnt;
        if(mx.FI<=n-m-mx.FI||mx.SE>=mx.FI-(n-m-mx.FI)) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
    return 0;
}