| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 690 人关注过本帖
标题:一道ACM的题求解
只看楼主 加入收藏
红糖水
Rank: 2
等 级:论坛游民
帖 子:42
专家分:11
注 册:2013-2-3
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:15 
一道ACM的题求解
Problem C
小媛在努力
时间限制:1000 ms  |  内存限制:65535 KB
描述
在多媒体数据处理中,数据压缩算法尤为重要。小媛上完课后就想自己发明一个数据压缩算法。她想呀想,终于想到一个方法。在多媒体数据中有很多数据都是重复的,所以她想把连续相同的数据用数据出现的次数和数据本身表示。例如:1 1 1 2 3 3 3 3 3  压缩后及为3 1 1 2 5 3(表示3个1,1个2和5个3)。有想法后小媛就希望把它用代码实现了。但是大家都知道小媛现在整天都忙着苦B的复习考研,连电脑都摸不到。所以她希望作为ACMer的你帮她写一下。
输入
输入包含多组数据,第一行一个数字T代表输入样例数。

每组样例开始一个数M < 10^7表示这组数据中数字的个数,接下来M个数表示要被压缩的数字(数字都不超过int表示的范围)。
输出
每组测试数据输出一行数字对,如上面描述的一样。两个数字之间用一个空格隔开。
样例输入
1
9 1 1 1 2 3 3 3 3 3
样例输出
3 1 1 2 5 3
搜索更多相关主题的帖子: 多媒体 
2013-02-04 17:19
心灯甚亮
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:2
帖 子:441
专家分:996
注 册:2013-1-29
收藏
得分:3 
样例输入
1
9 1 1 1 2 3 3 3 3 3
样例输出
3 1 1 2 5 3


这个9哪来的
2013-02-04 17:34
心灯甚亮
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:2
帖 子:441
专家分:996
注 册:2013-1-29
收藏
得分:0 
额,没看清题。
输入时利用缓冲区的特点,第一次读这组数据中数字的个数,然后用循环读M次数据即可完成输入(输入的不一定非得存储,可以边读边处理

[ 本帖最后由 心灯甚亮 于 2013-2-4 17:55 编辑 ]
2013-02-04 17:35
lz1091914999
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:四川
等 级:贵宾
威 望:37
帖 子:2011
专家分:5959
注 册:2010-11-1
收藏
得分:3 
建立一个链表,按顺序存放每个值和次数,最后输出。

My life is brilliant
2013-02-04 19:26
神龙赖了
Rank: 10Rank: 10Rank: 10
来 自:萨塔星
等 级:青峰侠
威 望:2
帖 子:711
专家分:1788
注 册:2012-10-13
收藏
得分:3 
程序代码:
#include <stdio.h>

#define MAX 100

int main(void)
{
    int num[MAX][MAX];
    int zip[MAX][MAX] = { 0 };
    int zipcount[MAX];
    int zip_col = 0;
   
    int i = 0;
    int column[MAX];

    int j = 0;
    int col = 0;
    int col_ = 0;
    char goout = 0;

    printf("Please enter the number:\n\n");
    scanf("%d",&i);

    /* input */
    for(j = 0; j < i; j++)
    {
        scanf("%d",&column[j]);   //接收需要读入的数字
       
        for(col = 0;col < column[j]; col++)
            scanf("%d",&num[j][col]);
    }

    /* 找到相同数字并统计储存 */
    for(j = 0; j < i; j++)
    {
        for(col = 0;col < column[j]; col++)
        {
            for(col_ = 0;col_ < col;col_++)
              if(num[j][col] == num[j][col_])  //如果前面有值等于它,说明已储存,跳过
                  goout = 1;
           
            if(!goout)
            {
            for(col_ = col; col_ < column[j]; col_++)
            if(num[j][col] == num[j][col_])
                zip[j][zip_col]++;            //测试这个数的出现次数
   
            ++zip_col;
            zip[j][zip_col++] = num[j][col];
            }
            goout = 0;
        }
        zipcount[j] = zip_col;  //储存索引值
        zip_col = 0;
    }

    /* output */
    printf("\n\nThe zip bug is in here:\n\n");
    for(j = 0; j < i; j++)
    {
        for(col = 0;col < zipcount[j]; col++)
        printf("%-2d",zip[j][col]);
        putchar('\n');
    }

    putchar('\n');
    return 0;
}
图片附件: 游客没有浏览图片的权限,请 登录注册

I have not failed completely
2013-02-04 20:59
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:3 
神龙朋友没实际玩过ACM吧。ACM对格式的要求非常严格,这道题其实都谈不上什么算法,更多的倒可以认为是格式控制的练习。

你的数组开的也太小了,注意一下题目中M的范围,我不太相信实际测试数据中会有这么大的(也许会有一组),但绝不会只有100这么小。

我猜这也是为什么李志选择用链表的原因之一。

你们可以按着自己的思路试一下,不过这题其实根本不需要用数组之类的大空间类型。

三五个整型变量,十来行代码,足矣。

重剑无锋,大巧不工
2013-02-04 21:33
不玩虚的
Rank: 9Rank: 9Rank: 9
来 自:四川
等 级:贵宾
威 望:10
帖 子:331
专家分:1301
注 册:2012-12-9
收藏
得分:3 
厉害啊

同学习......同进步....你帮我......我帮你.....上善若水.....
2013-02-04 22:09
zxyysy
Rank: 1
等 级:新手上路
帖 子:2
专家分:3
注 册:2013-1-21
收藏
得分:3 
你们是自学吗,我新手
学编程,在哪里学又好又快
2013-02-04 23:15
红糖水
Rank: 2
等 级:论坛游民
帖 子:42
专家分:11
注 册:2013-2-3
收藏
得分:0 
回复 6楼 beyondyf
大牛能否给出代码?
2013-02-05 09:35
大米稀粥客
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:82
专家分:155
注 册:2013-1-8
收藏
得分:0 
学习
2013-02-05 09:43
快速回复:一道ACM的题求解
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030433 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved