E. Accidental Victory （思维、二分）

ゝ一纸荒年。 2021-07-16 17:29 325阅读 0赞

[题目][Link 1]

思路：首先将数组排个序，容易知道要看一个数能不能成为冠军，其实就是将这个数从小到大不断与比他小于等于的数合并相加如果最终能够合并为一个数则其有成为冠军的机会。

在这我们先看看暴力的思路，就是遍历每一个数然后让它与最小的数开始相加直到最终它不能再和后面的数相加（前面所有的总和都比后面的某个数小）或合并为一个数了，O（n^2）这毫无疑问会超时。

我们想如何进行优化，其实在这我们可以发现对于两个数a<b，a会一直把前面小的数加完 而b也会把a加的那一部分数再加一次，这就重复进行了操作，这时我们可以先从最小的那个数按从小到大开始加（预定冠军为最小的那个数），当发现后面有一个数b前面所有相加都比其小，那么可以知道前面的数无论如何也不可能成为冠军，将预定的冠军设为b然后按之前操作继续合并，每次不能合并就将预定冠军改设，直到最后合并完所有的数，此时预定冠军所在的那个数往后的所有数都可能成为冠军。可以想一下因为每当无法相加预定冠军都会改设为新的能继续相加的数，到了最后的那个预定冠军必然是能够进行到最后相加的数，因为后面的数并没有出现能比其前面所有数相加都大的数，希望大家能理解，我也感觉自己说的有些绕，然后我是用map实现的。

#include<iostream>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    ll lst[Max];
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		map<ll, ll> ma;
    		int n;cin >> n;
    		for (int i = 1;i <= n;i++) { 
    			cin >> lst[i];ma[lst[i]]++;
    		}
    		ll sum = ma.begin()->first * ma.begin()->second;
    		ll mi = 0;
    		for (auto i = ++ma.begin();i != ma.end();i++)
    		{ 
    			if (sum < i->first)mi = i->first;
    			sum += i->first * i->second;
    		}
    		sum = 0;
    		for (int i = 1;i <= n;i++)if (lst[i] >= mi)sum++;
    		cout << sum << endl;
    		for (int i = 1;i <= n;i++)
    		{ 
    			if (lst[i] >= mi)cout << i << " ";
    		}
    		cout << endl;
    	}
    }

[Link 1]: https://codeforc.es/problemset/problem/1490/E