Codeforces Round #452 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #452 (Div. 2)
过题数：3
排名：802/8883

A. Splitting in Teams

题意

有 $n$ 组人要组队，每队 $3$ 个人，如果有一组人的人数为 $1$，那么这个人可以和任何人组队，如果一组人的人数为 $2$，那么这两个人要么在一组和别人组队，要么都不组队，问最多能组成多少个队。

输入

第一行为一个整数 $n~(2\leq n\leq2\times10^5)$，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq2)$，表示每组的人数。

输出

输出最多能组多少个三人队。

样例

题解

贪心地能让两人一组的和一人一组的组队就尽量让他们先组队，剩下的一人一组的再去组队。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
int n, num;
int cnt[3];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num);
            ++cnt[num];
        }
        int ans = min(cnt[2], cnt[1]);
        ans += (cnt[1] - ans) / 3;
        printf("%d\n", ans);
    }
    return 0;
}

B. Months and Years

题意

给出 $n$ 个数字，判这 $n$ 个数字是否等于某几个连续的月份的天数，按公历计算。

输入

第一行为一个整数 $n~(1\leq n\leq24)$，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(28\leq a_i\leq31)$。

输出

如果是，则输出 $Yes$，否则输出 $No$。

样例

题解

先预处理出八年连续的月份天数，然后暴力地去匹配天数。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 200;
int n;
int num[maxn];
int month[maxn] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int Month[maxn];
void Copy(int Index) {
    for(int i = 0; i < 12; ++i) {
        Month[Index + i] = month[i];
    }
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    for(int i = 0; i < 8; ++i) {
        Copy(i * 12);
        if(i % 4 == 3) {
            Month[i * 12 + 1] = 29;
        }
    }
    while(scanf("%d", &n) != EOF) {
        bool flag = false;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
        }
        for(int i = 0; i + n - 1 < 96; ++i) {
            bool f = true;
            for(int j = 0; i + j < 96 && j < n; ++j) {
                if(Month[i + j] != num[j]) {
                    f = false;
                    break;
                }
            }
            if(f) {
                flag = true;
                break;
            }
        }
        printf("%s\n", flag? "Yes": "No");
    }
    return 0;
}

C. Dividing the numbers

题意

将 $1$ 到 $n$ 总共 $n$ 个自然数分成非空的 $2$ 部分，要使得两部分各自数字的和相差最小，输出分配方案。

输入

输入只包含一个整数 $n~(2\leq n\leq6\times10^4)$。

输出

第一行输出最小的差值，第二行第一个数字表示其中一部分的数字个数 $cnt$，接下去 $cnt$ 个数字，表示被分到同一组的数字，可以按任意顺序输出，如果有多解输出任意一组。

样例

题解

可以发现只要连续的数字的个数为 $4$ 的整数倍就可以将数字分成两部分且它们的差值为 $0$，要使剩下的数字的差值最小，就对最小的几个数字进行分类讨论。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 60000 + 100;
int n;
void Print(int l, int r) {
    while(r > l) {
        printf(" %d %d", l, r);
        l += 2;
        r -= 2;
    }
    printf("\n");
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        if(n % 4 == 0 || n % 4 == 3) {
            printf("0\n");
            if(n % 4 == 0) {
                printf("%d", n / 4 * 2);
            } else {
                printf("%d 3", n / 4 * 2 + 1);
            }
        } else {
            printf("1\n%d 1", n / 4 * 2 + 1);
        }
        Print(n % 4 + 1, n);
    }
    return 0;
}