现在的位置: 首页 > 综合 > 正文

contest 1 F

2013年08月17日 ⁄ 综合 ⁄ 共 1355字 ⁄ 字号 评论关闭

题目:

Description
今天是小云的生日,小塘给小云送来了一些糖果。糖果装在一个连成一排的纸格子中(一
个格子中可能有多个糖果),不过在路上小塘掉了一些,所以有的纸格子是空的。
小云看到送来的糖果顿时就惊呆了,太多了,一下子肯定吃不完。由于纸格子没有盖子,
这时小云的爸爸就要小云按照他的要求用纸片把纸格子盖好(空格子没有糖果,所以能不盖
就不盖咯),以免里面的糖果受潮。
他说:“小云,我给你一定数量的纸片,纸片的数量是固定的,但是长度可以随你自己
来定,你告诉我用这个数量的纸片去盖住糖果,所用的纸片的最小总长度是多少。”
小云一看到这么多的糖果顿时就腿软了,聪明的你能帮助他吗?
举个栗子:
假设用4 个纸片覆盖下面的糖果:
答案很明显是4,4 个纸片覆盖的区间是:[1,1],[2,2],[3,3],[4,4]。
假设还是用4 个纸片覆盖下面的糖果:
答案则是9,4 个纸片覆盖的区间是:[1,3],[6,8],[11,11],[14,15]。
Input
输入包含多组测试数据,每组数据的第一行有三个数M(0<M≤S) 纸片的数量,
N(0<N<200000) 纸格子数量,S(0<S≤N) 糖果的数量。接下来的一行则是糖果所在的格子的
编号,格子编号从1 开始。当M,N,S 同时为0 时表示输入结束。
Output
输出最小的纸板总长度。

这道题是明显的贪心,想法很简单,就是先用一张纸把所有的有糖的格子盖住,但是要注意的是,盖的时候,端点一定要有糖,或者如果是空格子的话,那么直接将len初始化为0

然后,看空隙,也就是连续的空格,从多的开始删,每删一段,就是加一张纸

代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 200010;
int n, m, s;
bool vis[N];
struct seg { int i, j; } se[N];
bool cmp ( seg a, seg b ) {  return ( a.j-a.i ) > ( b.j-b.i ); }

int main()
{
    while ( scanf("%d%d%d", &n, &m, &s) != EOF && ( n || m || s ) ) {
        memset( vis, 0, sizeof(vis) );
        for ( int i = 1, x; i <= s; ++i ) {
            scanf("%d", &x);
            vis[x] = 1;
        }
        int st, en, id = 0, num = 1, i = 1, j = m;
        while( !vis[i] && i <= m ) i++;
        while( !vis[j] && j > 0 && j > i ) j--;
        int len = j - i + 1;
        while ( i <= j ) {
            //printf("ok\n");
            if ( !vis[i] ) {
                st = i;
                for ( i++; i <= j; ++i ) if ( !vis[i] ) continue; else break;
                en = i;
                se[id].i = st, se[id++].j = en;
                //printf("%d %d\n", st, en);
            }
            else i++;
        }
        sort( se, se + id, cmp );
        for ( int i = 0; i < id && num < n && len > 0; ++i ) {
            len -= (se[i].j - se[i].i);
        //printf("%d\n", id);
            num++;
        }
        printf("%d\n", len);
    }
}


抱歉!评论已关闭.