题解AT_arc211_a 【[ARC211A] Banned X 2】

· · 题解

由于周日已经知道自己基本上要成为 FJ 的 NOIP 省三 前几名了， AFO 了 ，晚上打个 ARC 玩玩。我的 OI 生涯：2023.2-2025.11.30。

本蒟蒻第二次打 ARC。

题目传送门

思路

诈骗题

很容易想到，我们可以贪心地将相同的数放在一起。

注意到 5 是最特殊的，因为它不能连续放，因此可以考虑先放 1 个 5，然后把 5 穿插放在别的数中间。如果 5 的数量比较多，肯定能插满所有数，别的数就不会有冲突，剩下的 5 就塞一些别的数穿插，答案就是 5 的数量减去别的数的数量再减 1；否则如果数量较少，就将别的数升序排序，此时除去 5 很明显最多只会有 1 个中间的地方冲突，先把 1 个 5 放在冲突的两个数中间，剩下如果还有 5 就仍然间隔着别的数放直到放完。

如果没有 5，那么有冲突的只可能当只有 2 个数且这两个数刚好和为 10 时，将相同的数放在一起，只有中间会冲突，答案为 1。

代码

AC Code：（C++23）

#include<iostream>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<numeric>
#include<vector>
#include<queue>
using namespace std;
int T,cnt,id,ans;
long long sum;
int a[15];
int main() {
  scanf("%d",&T);
  while(T--) {
    sum=cnt=0;
    for(int i=1;i<=9;i++) {
      scanf("%d",a+i);
      if(i!=5)
        sum+=a[i];
    }
    for(int i=1;i<=4;i++)
      if(max(a[i],a[10-i])) {
        cnt++;
        id=i;
      }
    if(cnt==1 && a[id] && a[10-id] && a[5]==0)
      puts("1");
    else {
      ans=max(0ll,a[5]-sum-1);
      printf("%d\n",ans);
    }
  }
}

Atcoder AC 记录