Andrewei's Blog
0%

Codeforces Round #251 (Div. 2)

发表于 更新于 分类于 ， 阅读次数： 17

比赛链接: http://codeforces.com/contest/439

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个整数表示 ti(1<=t<=100), 表示这n首歌的时间，问在保证 Devu 把所有歌唱完的情况下，Churu 最多可以讲多少个笑话，如果 Devu 不能把 n 首歌唱完，输出 -1.

解题思路:

Devu 唱完n首歌共需要时间 T=∑i=1nti+10(n−1), 此时 Churu 可以讲的笑话为 ans=2(n−1)+(d−T)/2.

参考程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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<=105) 个科目，每个科目有 ci(1<=i<=n) 个章节, 他学习有个特点，在学习第一个科目的时候每个章节的学习时间为x, 学习第二个科目的时候学习每个章节的时间为x−1, 一次类推，x 递减，直到x==1时，他的学习速度将维持不变, 问他学完这n个科目所需要的最小时间为多少.

解题思路:

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

参考程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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<=105,0<=p<=k)表示有n个整数ai(1<=ai<=109)，要把这些整数分成恰好k组，并且满足和为偶数的组的数目为p, 问有没有一种方案可以满足题目要求， 有的话输出YES, 并输出任意一种方案, 没有的话，输出NO.

解题思路:

构造题:

  1. 先考虑构造k−p组奇数，首先每个奇数为一组, 如果不够k−p 组输出 NO.
  2. 如果多余的奇数的个数为奇数个，输出 NO, 如果多余奇数的个数的一半加上所有偶数的个数小于p, 输出NO;
  3. 将多余的奇数两两一组作为和为偶数的分组;
  4. 每个偶数作为一个和为偶数的分组直到凑够p组，多余的偶数放在最后一组即可。
    参考代码:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    #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;
    }

Gitalk 加载中 ...