【Codeforces 1149 A】Prefix Sum Primes

题意:给\(n\)个数,每个是\(1\)或\(2\),现在要把它们排列,使得所有前缀和中质数数量最多。

思路:首先我们知道质数除了\(2\)都是奇数。

那么我们最多的时候就是有2、3、5、7、。。。

就是\(2,1,2,2,...\)这种排列,或者\(1,1,1,...\)这种。

就是看是否存在2就好了。

稍微根据\(1\)、\(2\)的个数分类讨论一下就好了,就像

if (cnt2) {
    printf("2 "); -- cnt2;
    if (cnt1) {
        printf("1 "); -- cnt1;
        while (cnt2 --) printf("2 ");
        while (cnt1 --) printf("1 ");
    } else {
        while (cnt2 --) printf("2 ");
    }
} else {
    while (cnt1 --) printf("1 ");
}

这样。

上一篇:基于MVC架构登录案例分析研究


下一篇:01序列