大致难易程度补题.
A - A Hero Named Magnus
题意
如果选择$ban$掉猛犸,这一把赢的可能性为$1$,否则赢的可能性是$50$%(已知作者不打英雄联盟).
给定比赛中第$x$次$ban$掉猛犸,问最坏需要打多少场才能获得胜利.
思路
结果为$2 \times x-1$,在$x$场之前的比分为$0:x-1$,在此之后都是必赢,即需要再打$x$次比赛能获得胜利.
注意开$long$ $long$.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int t;
ll n;
int main()
{
cin >> t;
while(t--)
{
cin >> n;
cout << 2*n-1 << endl;
}
return 0;
}
I - PTSD
题意
给定$n$个士兵,从$1,2,…,n$编号,每个士兵$i$有权值为$i$,给定一个$01$序列,表示每个是否存在$PTSD$疾病.
将这些分为几组,同一组内如果存在比存在$PTSD$疾病权值更大的士兵,则他会感到失望.求最大化分组后各组失望士兵的权值和更大.
思路
贪心,要使满足条件的权值和最大,要让失望的士兵分布在尽可能多的组,因此考虑两两配对.用$cnt$变量存储当前未配对的士兵,按照权值从大到小枚举,如果当前士兵存在$PTSD$疾病且$cnt>0$,则进行分在一组,否则$cnt+1$,同理没有$PTSD$的士兵直接$cnt+1$即可.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 1000010
using namespace std;
typedef long long ll;
int t,n;
long long res,cnt;
char s[MAXN];
int main()
{
cin >> t;
while(t--)
{
res=cnt=0;
cin >> n >> s+1;
for(int i=n;i>=1;i--)
{
if(s[i]=='0')
cnt++;
else if (s[i]=='1')
{
if(cnt>0)
cnt--,res+=i;
else cnt++;
}
}
cout << res << endl;
}
return 0;
}
