硬币游戏

根据题目意思，非常容易想到，如果是硬币最多的那个人，肯定是可以获胜的，硬币第二多的人肯定可以赢得硬币数量第三到第$nn$多的人的所有的硬币，所以只要把剩下的硬币全部加起来，再和最多的比较，判断能不能获胜， 以此类推，如果 $a[i]a[i]$ 要赢过赢得硬币数量多的人，就必须先得到比 $a[i]a[i]$ 个硬币少的人的硬币，再和比$a[i]a[i]$多的人比较大小。

换个角度思考：就是按照硬币数量从小到大排序后，对于每个人，显然可以赢得自己左边所有的硬币，于是自己的硬币就变成了自己左边所有硬币的和再加上自己的硬币，再和右边的一个一个比较，如果可以一直赢到最后一个人，就可以获胜，

也就是说，排序后，如果某个人得到了他左边的所有的硬币之后还是比他右边的第一个人少，那么他和他左边的所有人都无法获胜（注意理解）。

明白这些之后，这题就变得简单了，首先排序，再用前缀和记录比自己小的和自己的硬币数量 $num[i]num[i]$，最后从后往前比较，找到第一次出现 的位置即可。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

const int N = 1e6 + 7;

pair<int, int> a[N]; //因为最后要输出位置，所以用pair记录a[i]的值和位置
long long num[N];//用于计算前缀和
vector<int> ans;// 最后统计数量

void solve() {
    int n;
    while(cin >> n) {//注意多组输入
        for(int i = 1; i <= n; ++ i) cin >> a[i].first, a[i].second = i;
        sort(a + 1, a + n + 1); num[1] = a[1].first;
      
        for(int i = 2; i < n; ++ i) num[i] = num[i - 1] + a[i].first;//计算前缀和
      
        for(int i = n - 1; i > 0; -- i) {
            if(num[i] < a[i + 1].first) break; //遇到第一个前缀和都比后一个数小直接退出
            ans.push_back(a[i].second); 
        }
        ans.push_back(a[n].second);  //注意最大的一定可以获胜
      
        cout << ans.size() << endl;
        sort(ans.begin(), ans.end());
        for(int i = 0; i < ans.size(); ++ i) cout << ans[i] << " ";
        cout << endl;
        ans.clear();//多组输入记得清空vector
    }
}

signed main() {
    int t  = 1;
    while(t --) solve();
}