题解归档 - cf2230C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2230C
• 本地来源：problems/cf2230C/idea.md
• 题目链接：https://codeforces.com/contest/2230/problem/C
• 原始标题：cf2230C

思路

cf2230C

pattern: circular runs with forbidden singleton runs.

claim: Use every color with count at least 2 completely. Let q be the number of colors with count 1. If there is one heavy color of size m, it can host floor(m/2) singleton colors. If there are at least two heavy colors, a heavy block of size m can host floor(m/2)-1 singleton colors. The answer is the heavy total plus the number of hosted singleton colors, unless fewer than three cards are possible.

necessary: Compress the circle into maximal runs. A bad triple appears exactly when a run of length 1 has two different neighboring colors. Therefore a singleton color must be placed between two runs of the same heavy color. If there are other heavy blocks outside this split chain, every segment of the hosting heavy color touching a singleton must have length at least 2, giving floor(m/2)-1 capacity. With only one heavy color, the cyclic chain needs two cards per singleton, giving floor(m/2).

sufficient: Put all heavy colors as blocks of length at least 2. Then split heavy blocks into segments of length at least 2 and insert hosted singleton colors between two segments of the same heavy color. Every length-3 window either contains two cards from a length-at-least-2 segment, or is centered at a singleton between equal colors.

brute/check: For small total card counts, enumerate selected counts and all unique circular permutations, then compare with the formula.

edge: All counts equal 1 gives 0. One color with count 2 alone gives 0, but count 2 plus one singleton gives 3.

代码

来源：problems/cf2230C/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll s[maxn+5];
int main(){
    ll t,n,i,zc,cnt,cur,ans;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        zc=cnt=cur=ans=0;
        for(i=1;i<=n;i++){
            scanf("%lld",&s[i]);
            if(s[i]==1) zc++;
            else{
                cnt++;
                ans+=s[i];
                cur+=s[i]/2-1;
            }
        }
        if(cnt==0){
            printf("0\n");
            continue;
        }
        if(cnt==1){
            ans=s[n]+min(zc,s[n]/2);
            if(ans<3) ans=0;
            printf("%lld\n",ans);
            continue;
        }
        ans+=min(zc,cur);
        printf("%lld\n",ans);
    }
    return 0;
}