比赛编号太臭了

牛客练习赛114 D题题解

MyBlog

对一第一组数据,我们形象化的得到下图:

如何拆解使其变成一个“顺子”呢,我们像这样:

贪心的从后往前取,对于取数列时的终点也就是枚举的起点如果不为 0 ,就向前一直取,如果取到一个数 发现这个数的个数 是大于的,就停止,最后看拆出来的数列长度是否都大于等于 5 。


void work()
{
    n = read();
    for(int i = 1; i <= n; i++)
        num[i] = 0;
    for(int i = 1; i <= n; i++)
    {
        int x = read();
        num[x]++;
    }
    for(int i = n; i >= 1; i--)
    {
       while(num[i])
       {
            int cnt = 0;
            for(int j = i; j >= 1; j--)
            {
                num[j]--;
                cnt++;
                if(num[j - 1] < num[j] + 1)
                    break;
            }
            if(cnt < 5)
            {
                printf("NO\n");
                return;
            }
        }
    }
    printf("YES\n");
    return;
}