Codeforces Round #251 (Div. 2)

A题(Devu, the Singer and Churu, the Joker)

题目大意:

Devu 喜欢唱歌，唱一首歌的时间为 t, 每唱完一首歌至少要休息 10 分钟，Churu 喜欢讲笑话，讲一个笑话的时间为 5 分钟, 现给定两个整数 $n(1 <= n <= 100) d(1 <= d <= 10000)$, 分别表示Devu在个人演唱会上要唱 n 首歌，演唱会的总时间为 $d$, 接下来给定$n$个整数表示 $t_i(1 <= t <= 100)$, 表示这$n$首歌的时间，问在保证 Devu 把所有歌唱完的情况下，Churu 最多可以讲多少个笑话，如果 Devu 不能把 $n$ 首歌唱完，输出 -1.

解题思路:

Devu 唱完$n$首歌共需要时间 $T=\sum_{i=1}^{n}t_i+10(n-1)$, 此时 Churu 可以讲的笑话为 $ans=2(n-1)+(d-T)/2$.

参考程序:

#include <cstdio>
int main(){
    int n, d;
    while(scanf("%d%d", &n, &d) != EOF){
        int sum = 0, v;
        for(int i = 0; i < n; i++){
            scanf("%d", &v);
            sum += v;
        }
        sum += (n - 1) * 10;
        if(sum > d) printf("-1\n");
        else{
            int tmp = d - sum;
            int ans = 2 * (n - 1) + tmp / 5;
            printf("%d\n", ans);
        }
    }
    return 0;
}

B题(Devu, the Dumb Guy)

题目大意:

Devu 学习东西很慢, 现在他要学习$n(1 <= n <= 10^5)$ 个科目，每个科目有 $c_i(1 <= i <= n)$ 个章节, 他学习有个特点，在学习第一个科目的时候每个章节的学习时间为$x$, 学习第二个科目的时候学习每个章节的时间为$x - 1$, 一次类推，$x$ 递减，直到$x == 1$时，他的学习速度将维持不变, 问他学完这$n$个科目所需要的最小时间为多少.

解题思路:

贪心，先学习章节少的科目，然后学习章节多的科目, 注意答案会超出 int 范围。

参考程序:

#include <algorithm>
using namespace std;
const int MAXN = 100010;
long long a[MAXN];

int main(){
    int n, x;
    while(scanf("%d%d", &n, &x) != EOF){
        for(int i = 0; i < n; i++)
            scanf("%I64d", &a[i]);

        sort(a, a + n);

        long long ans = 0;
        for(int i = 0; i < n; i++){
            ans += a[i] * x;
            if(x > 1) x--;
        }

        printf("%I64d\n", ans);
    }
    return 0;
}

C题(Devu and Partitioning of the Array)

题目大意:

给定三个整数$n, k, p(1 <= k <= n <= 10^5, 0 <= p <= k)$表示有$n$个整数$a_i(1 <= a_i <= 10^9)$，要把这些整数分成恰好$k$组，并且满足和为偶数的组的数目为$p$, 问有没有一种方案可以满足题目要求，有的话输出YES, 并输出任意一种方案, 没有的话，输出NO.

解题思路:

构造题:

先考虑构造$k-p$组奇数，首先每个奇数为一组, 如果不够$k-p$ 组输出 NO.
如果多余的奇数的个数为奇数个，输出 NO, 如果多余奇数的个数的一半加上所有偶数的个数小于$p$, 输出NO;
将多余的奇数两两一组作为和为偶数的分组;

每个偶数作为一个和为偶数的分组直到凑够$p$组，多余的偶数放在最后一组即可。
参考代码:

#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 100010;

vector <int> ans[MAXN];
int n, k, p, eNum, oNum;
int even[MAXN], odd[MAXN];

void init(){
    for(int i = 0; i < MAXN; i++)
        ans[i].clear();
    eNum = oNum = 0;
}

bool solve(){
    int i = 0, dx = 0;
    if(oNum < k - p) return false;
    for(i = 0; i < k - p; i++)
        ans[dx++].push_back(odd[i]);
    if((oNum - i) & 1) return false;
    if((eNum + ((oNum - i) >> 1)) < p) return false;
    for(; i < oNum; i += 2){
        if(dx == k) break;
        ans[dx].push_back(odd[i]);
        ans[dx++].push_back(odd[i + 1]);
    }
    if(dx == k){
        for(; i < oNum; i += 2){
            ans[dx - 1].push_back(odd[i]);
            ans[dx - 1].push_back(odd[i + 1]);
        }
        for(i = 0; i < eNum; i++)
            ans[dx - 1].push_back(even[i]);
    }else{
        for(i = 0; i < eNum; i++){
            if(dx < k) ans[dx++].push_back(even[i]);
            else ans[dx - 1].push_back(even[i]);
        }
    }
    return true;
}

int main(){
    while(scanf("%d%d%d", &n, &k, &p) != EOF){
        init();
        int v;
        for(int i = 0; i < n; i++){
            scanf("%d", &v);
            if(v & 1) odd[oNum++] = v;
            else even[eNum++] = v;
        }
        if(solve()){
            printf("YES\n");
            for (int i = 0; i < k; i++) {
                int t = ans[i].size();
                printf("%d", t);
                for (int j = 0; j < t; j++)
                    printf(" %d", ans[i][j]);
                printf("\n");
            }
        } else printf("NO\n");
    }
    return 0;
}