P17716 [HexOI Round 1] 变魔术 / magic [题解]

Mid_night_ · 2026-10-22 16:53:22 · 题解

P17716 [HexOI Round 1] 变魔术 / magic [题解]

Solution

主要涉及贪心。

• 赛时思路： 对于每个数 a_i 找到所有小于等于它的数，再次加到优先队列中，然后不停重复，直到成为最大值则当前值可以被选择，时间复杂度为 O(N^2 \log N)。

• 正解：

  我们先将 a 升序排列。

  1. 我们先将 a 这样分组 \{a_1,a_2,a_3...a_{n-1}\}\{a_n\} 来删掉 a_n。
  2. 然后 \{a_1,a_2,a_3...a_{n-2}\}\{a_{n-1}\} 来删掉 a_{n-1}。
  3. 以此类推，依次删掉 n,n-1,...,x+1。
  4. 最后将剩下的元素按 \{1\}\{2\}...\{x\} 的顺序分组保留 x。

  可以证明此策略正确。

  倒序扫描序列，当我们遍历到 x，如果 sum_x<a_{x+1}，说明无论如何都无法保留 1,2,3,...,x 这些数，直接跳出循环输出即可。

  时间复杂度 O(N)。

  Code

  ::::success[Code]

  #include<bits/stdc++.h>
  using namespace std;
  #define int long long
  const int N = 1e5+5;
  int n,m;
  int s[N];
  int f[N];
  struct node{
    int num,id;
  }a[N];
  bool cmp(node A,node B){
    return A.num<B.num;
  }
  signed main(){
    cin>>n;
    for(int i = 1;i<=n;i++){
        scanf("%lld",&a[i].num);
        a[i].id = i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i = 1;i<=n;i++){
        s[i] = s[i-1]+a[i].num;
    }
    s[0] = -1;
    for(int i = n;i>=0;i--){
        if(s[i]<a[i+1].num){
            for(int j = 1;j<=i;j++) f[a[j].id] = 0;
            for(int j = i+1;j<=n;j++) f[a[j].id] = 1;
            break;
        }
    }
    for(int i = 1;i<=n;i++){
        cout<<f[i]<<' ';
    }
    return 0;
  }

  ::::