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

zck0710 · 2026-10-19 20:23:48 · 题解

题意简述

给定数组 a_1\sim a_n，对每个下标 i，问是否存在操作策略，最后只保留第 i 块积木。 操作规则：

1. 将当前手上积木任意分成若干堆；
2. 保留总和最大的一堆，其余淘汰；
3. 重复直到只剩一块。

思路

1、暴力

如果考试遇到，我肯定优先考虑暴力（正解想不出 QwQ）。我们先将数组排序从小到大排序，总和 cnt=\sum a_i。我们尝试从大到小不断扔掉元素：

设当前手里总和为 now，现在想扔掉一个元素 y：

Q：那我们什么时候可以把 y 淘汰掉呢？

A：把 y 单独成一堆，剩下所有东西作为另一堆。剩下一堆总和是 now-y，只要 now-y \ge y，就可以保留剩下那堆，丢掉 y。

从最大的元素开始依次尝试丢弃：

• 如果满足条件，就把 y 丢掉，now\leftarrow now-y；
• 一旦遇到不能丢的，直接停止。 最后如果剩下的总和恰好等于目标元素的值，代表可以只留下它，答案为 1。

::::info[60 分暴力]

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct S{int v,id;};
bool cmp(S x,S y){
    return x.v<y.v;
}
signed main(){
    int n,cnt=0;
    cin>>n;
    vector<S> a(n);
    vector<int> pre(n+1,0);
    vector<int> ans(n,0);
    for(int i=0; i<n; i++) {
        cin>>a[i].v;
        a[i].id=i;
        cnt+=a[i].v;
    }
    sort(a.begin(),a.end(),cmp);
    for(int i=0; i<n; i++) pre[i+1]=pre[i]+a[i].v;
    for(int i=0; i<n; i++) {
        int now=cnt;
        for(int j=n-1; j>=0; j--) {
            if(j==i) continue;
            int y=a[j].v;
            if((now-y)*2>=now)now-=y;
            else break;
        }
        if(now==a[i].v) ans[a[i].id]=1;
    }
    for(int i=0; i<n; i++) cout<<ans[i]<<" ";
}

2、AC 做法

考虑前缀和，并且使用双指针优化。仍然是将数组从小到大排序，得到 b_0\le b_1\le\cdots\le b_{n-1}，将数组升序排序，定义前缀和：

记 C_i=\sum_{k=0}^i b_k，则目标 b_i 可行的充要条件：