CCF NOI1134 奶牛晒衣服

时间限制: 1000 ms 空间限制: 262144 KB

题目描述

在熊大妈英明的带领下，时针和它的同伴生下了许多牛宝宝。熊大妈决定给每个宝宝都穿上可爱的婴儿装。于是，为牛宝宝洗晒衣服就成了很不爽的事情。
圣人王担负起了这个重任。洗完衣服后，你就要弄干衣服。衣服在自然条件下用1的时间可以晒干A点湿度。抠门的熊大妈买了1台烘衣机。使用烘衣机可以让你用1的时间使1件衣服除开自然晒干的A点湿度外，还可烘干B点湿度，但在1的时间内只能对1件衣服使用。
N件衣服因为种种原因而不一样湿，现在告诉你每件衣服的湿度，要你求出弄干所有衣服的最少时间（湿度为0为干）。

输入

第一行N,A,B；接下来N行，每行一个数，表示衣服的湿度（1<=湿度，A，B<=500000，1<=N<=500000）。

输出

一行，最少时间。

样例输入

3 2 1

样例输出

数据范围限制

1<=湿度，A，B<=500000，1<=N<=500000

提示

第1时间内，用机器处理第3件衣服，此外，所有衣服自然晒干2。花费1时间全部弄干。

问题分析

这是一个模拟计算问题，按照时间进行模拟即可。

关键是理解题意。

程序说明

有关说明，参加源程序。

要点详解

理解题意最为重要。

参考链接：（略）。

100分通过的C语言程序：

#include <stdio.h>
#include <string.h>

#define N 500000
int count[N+1];

int main(void)
{
    int n, a, b, val, max, i;

    memset(count, 0, sizeof(count));

    scanf("%d%d%d", &n, &a, &b);

    // 输入数据，并且统计各种湿度的衣服数量，求出最大湿度
    max = 0;
    for(i=1; i<=n; i++) {
        scanf("%d", &val);

        count[val]++;

        if(val > max)
            max = val;
    }

    // 模拟：按时间，1个时间1个时间进行模拟
    int ans = 0;
    while(ans * a < max) {  // 1时间自然晒干的a点湿度：所以只需要处理目前湿度大于ans*a的
        ans++;

        // 1时间1件衣服可烘干B点湿度：有1件衣服湿度减少了，或者已经干了
        count[max]--;

        // 过有1时间后，衣服湿度减少b；若max-b不为0，则湿度为max-b的衣服增加1件
        if(max - b > 0)
            count[max - b]++;

        // 先处理衣服湿度最大的，然后依次处理次之，直到处理完
        while (count[max] == 0)
            max--;
    }

    printf("%d
", ans);

    return 0;
}