PTSD题解

题目链接：PTSD

题意：

共n个样例。每个样例给定一个长度为m的01序列，第i个位置具有的能量为i。我们可以将任意点划分到一个组中，假设其中能量第二高的点的能量为k，如果它在原序列中的所在位置被1标记，那么这个组中的能量为k。问我们最高能获得多少能量。

思路：

• 因为只有组中第二高且被1标记的点可以贡献能量，那么我们可以通过两两配对的方式，尽量多分组。
• 从高到低开始遍历，用cnt记录待配对的点个数。其中被0标记的点无法贡献能量，所以可以直接加入待配对行列。每当遇到一个被1标记的点，我们就看cnt是否不为0，如果是，那么就直接配对，cnt - -（也即待配对数量减1），否则我们将其加入待配对行列。
• 数据范围是1e6，最后的和会超int，要用long long 来存答案。

代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<set>

using namespace std;
typedef pair<int, int > PII;
typedef long long ll;

const int N = 1e6 + 10;

int n;

int main()
{
	cin >> n;
	while (n--)
	{
		int m;
		string s;
		cin >> m >> s;
		int cnt = 0;
		ll num = 0;
		for (int i = s.size() - 1; i >= 0; i--)
		{
			if (s[i] == '0')cnt++;
			else
			{
				if (cnt > 0)
				{
					num += (i + 1);
					cnt--;
				}
				else cnt++;
			}
		}

		printf("%lld\n", num);
	}

	return 0;
}