Straight Master Gym-101775J (思维+差分)

题意:给出N种类的数量,求是否可以把N种牌按3-5张连续的顺子打出,顺子必须连续.

分析:相当于把这个序列分成若干长度为[3,5]的区间,当然其实分成若干段大于3的区间即可.因为大于5的区间又可以分拆成若干段长度为[3,5]的区间.

令\(b[i] = a[i] - a[i-1]\), 则\(b[i] >0\) 表示有\(b[i]\)段区间以此为起点, \(b[i] < 0\)表示有\(|b[i]|\)段区间以\(i-1\)为终点. 那么对于每个区间的起点i,必须在i+3开始的位置一直向后寻找终点,且起点和终点必须数量相等,若不相等则不能打出顺子.

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 2e5+5;

LL a[MAXN], b[MAXN];

int N;

bool check()

{

    LL sum = 0;

    if(b[2] <0 || b[3]<0) return false;

    for(int i=1;i<=N+1;++i){

        int p = i + 3;

        if(b[i] > 0) sum += b[i];

        if(p > N+1) break;

        if(b[p]<0 ){

            sum += b[p];

            b[p] = 0;

        }

        if(sum<0) break;

    }

    if(sum !=0) return false;

    return true;

}

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt", "r", stdin);

        freopen("out.txt", "w", stdout);

    #endif

    int T,cas=1; scanf("%d",&T);

    while(T--){

        scanf("%d", &N);

        for(int i=1;i<=N;++i){

            scanf("%lld", &a[i]);

            b[i] = a[i] - a[i-1];

        }

        b[N+1] = -a[N];

        printf("Case #%d: ",cas++);

        if(check()) printf("Yes\n");

        else printf("No\n");

    }

    return 0;

}

巴特西

Straight Master Gym-101775J (思维+差分)

最新文章

热门文章