原题链接：Problem - C - Codeforces
题意（这里我将题意等价转换了下，所以和原题描述有点出入，但是效果是一样的）：
给你一个n和m，然后对于1<=i<=n依次给出a[i]。在一开始，第i个人会赢i场，但是你可以选择任意k个不同的a[i]，并且满足这k个a[i]的和小于m，然后你就可以让这k个a[i]对应位置的胜场减一，并且你的胜场为变为k，也就是你选择a[i]的数目。求你能达到的最好名次。
举个例子，比如样例五的数据：
4 4
1 2 2 1
对于每个a[i]的初始胜场为：
1 2 3 4?
然后你就可以选择i=1，i=3，i=4，因为a[1]+a[3]+a[4]=1+2+1<=4，所以可以这么选。然后你的胜场即为3场，因为你赢了三个人。并且由于你击败了这三个人，所以a[1]，a[3]，a[4]对应位置上的胜场减一，就变成了：
0 2?2 3
而又因为你的胜场为3场，所以你和a[4]并列第一。
思路：?通过题意我们可以发现，我们只能让一个人的胜场最多减一，而又因为每个人的初始胜场是不同的，所以我们最多能让一个原本胜场比你多的人变得和你胜场数一样，而且那个人只能是第（你的胜场数+1）个人，因为后面人的胜场都至少比你大2场，而我们最多让一个人的胜场减1，所以只有这个人。那么这个结论有什么用呢？通过这个结论我们可以推出，若我们选择了k个人比赛，并且我们选择了这个第（k+1）人，那么我们的排名就可以上升一名，也就是说，若原本我们的排名是n-k+1，但是我们又选择了这个第（k+1）人的话，我们的排名就能变成n-k。
所以我们可以倒着枚举赢的场次来求出最好名次，具体实现见代码底部注释。
void solve() { map<int, int> mp; int n, m; cin >> n >> m; FOR(1, n) cin >> a[i].first, a[i].second = i; sort(a + 1, a + n + 1); FOR(1, n) { sum[i] = sum[i - 1] + a[i].first; mp[a[i].second] = i;//存储原本位置的人在现在的哪个位置 } ROF(n, 1) { if (m >= sum[i] || sum[i - 1] <= m && mp[i] <= i - 1 ||mp[i] >= i && sum[max(0ll, i - 2)] + a[mp[i]].first <= m) { cout << n - i + 1 << endl; return; } } cout << n + 1 << endl; } //m >= sum[i] 表示我们可以直接打赢这i个人 // sum[i - 1] <= m && mp[i] <= i - 1表示第k+1人在我们赢的人里，所以我们赢i-1场就够了 //上段解释中，因为我们选择了赢i-1场，所以k+1就是i，mp[i]就是第k+1人的位置 // sum[max(0ll, i - 2)] + a[mp[i]].first <= m表示若第k+1人不在我们赢的人里，我们需要将它选择，然后赢i-2场加上第k+1场，总共i-1场就行了
 1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。 |
标签： #Educational #codeforces #Round #141 #Rated #for #div #2
