2021 CCPC 桂林站 I.PTSD

Problem Analysis

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

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

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

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

Accepted Code

#include 
#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