2021 CCPC 桂林站 I.PTSD

Problem Analysis

题目大意：有$n$个士兵，从$1\dots n$编号，每个士兵拥有一个权值为$i$。然后给定一个$0-1$序列，表示每个士兵是否被标记。

现在要将这些士兵分为几组，同一组内如果存在比被标记的士兵权值更大的士兵，那么该士兵就会感觉到失望。要求最大化分组后各组失望士兵的权值和最大。

思路分析：要使得权值和最大，那么要让失望的士兵分布在尽可能多的组里。因此考虑两两配对。我们设置一个$cnt$变量表示未被配对的士兵，并将所有士兵按照权值从大到小进行排序。遍历排之后的序列，如果当前的士兵被标记$cnt>0$ ，且仍有未被配对的士兵，那么就进行配对。如果当前的士兵未被标记，那么直接加入等待配对的序列中。

由于我们已经按照权值从大到小进行排序过了，因此可以保证每次配对的士兵权值一定大于当前士兵的权值，也就是当前士兵一定会失望。

Accepted Code

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

const int N = 1e6 + 10;

struct node{ bool st; int ser; }a[N];

inline void solve(){
    int n = 0, cnt = 0, ans = 0; cin >> n;
    string str; cin >> str; str = ' ' + str;
    for(int i = n; i; i--){
        if(str[i] == '1'){
            if(cnt) cnt--, ans += i;
            else cnt++;
        }
        else cnt++;
    }
    cout << ans << endl;
}

signed main(){
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}

最后

以上就是单身母鸡为你收集整理的2021 CCPC 桂林站 I.PTSD的全部内容，希望文章能够帮你解决2021 CCPC 桂林站 I.PTSD所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。