1520: 压缩编码

时间限制: 1 Sec  内存限制: 2 MB
提交: 107  解决: 54
[提交][状态][讨论版]

题目描述

  某工业监控设备不断发回采样数据。每个数据是一个整数(0到1000之间)。各个数据间用空白字符(空格,TAB或回车换行)分隔。
  因为大多数时候,相邻的采样间隔数据是相同的,可以利用这个特征做数据的压缩存储。其方法是:对n(n>1)个连续相同的数字只记录n和该数字本身;对m(m>0)个连续不重复的数字,则记录 m*-1 和这些数字本身(之所以用负数,是为了与第一种情况区分,便于解压缩)。
 
    例1:
    假设采样数据为:
    12 34 34 25 25 25 25 11 15 17 28 14 22 22 22 
    则将上述采样数据按照上述规则进行压缩编码后的数据为:
    -1 12 2 34 4 25 -5 11 15 17 28 14 3 22
 
 
 
 
    例2:
    假设采样数据为:
    12 13 14 13 12
    则将上述采样数据按照上述规则进行压缩编码后的数据为:
    -5 12 13 14 13 12
    例3:

    假设采样数据为:
    66 66 66 66 66 88 88 88 88 88 88 88 88 88 88 88 
    则将上述采样数据按照上述规则进行压缩编码后的数据为:
    5 66 11 88

输入

先输入采样数据的个数n(1<=n<=10000)。

然后输入n个采样数据。每个数据是一个整数(0到1000之间,包括0和1000本身)。各个数据间用空白字符(空格,TAB或回车换行)分隔。

输出

输出按规则进行压缩编码后的数据,数据之间用一个空格隔开。

注意,最后一个输出数据之后,没有空格,而是换行符。

样例输入

16
12 34 34 25 25 25 25 11 15 17 28 14 22 22 22 13

样例输出

-1 12 2 34 4 25 -5 11 15 17 28 14 3 22 -1 13
#include<iostream>
#include<cstring>
#include<cstdio> using namespace std;
const int N = + ; int cnt[N], a[N], n;
void Solve_question(){
memset(cnt, , sizeof(cnt));
a[] = -;
int cur = , x;
for(int i = ; i <= n; i++){
scanf("%d", &x);
if(x != a[cur]){
a[++cur] = x;
cnt[cur] = ;
}else{
cnt[cur]++;
}
}
x = ;
for(int i = cur; i >= ; i--){
if(cnt[i] == && cnt[i-] != ){
cnt[i] = -x;
x = ;
}else if(cnt[i] == && cnt[i-] == ){
x++;
cnt[i] = ;
}
}
x = ;
for(int i = ; i <= cur; i++){
if(cnt[i])
printf("%d ", cnt[i]);
printf("%d%c", a[i], i==cur?'\n':' ');
}
}
int main(){
while(scanf("%d", &n) == ){
Solve_question();
}
return ;
}
 

最新文章

  1. R语言基本操作函数---变量的基本操作
  2. Python学习之路—Day1
  3. oracle增量备份
  4. C++学习笔记5:如何给变量及函数命名?
  5. ajax提交后完全不进入action直接返回错误
  6. 网络加速手段之一,JS文件资源合并下载
  7. Spock Proxy
  8. JS它DOM
  9. AngularJS之使用服务封装
  10. 用python3实现linux的sed功能
  11. ⑧bootstrap组件 文字图片 下拉菜单 按钮组 使用基础案例
  12. 2018年的UX设计师薪酬预测,你能拿多少?
  13. Linux的ls命令在Windows中的应用
  14. CRM客户关系管理系统(五)
  15. IP 协议
  16. [JOISC2014]電圧
  17. 以添加评论组件为例看angular2请求数据的处理
  18. PHP -S命令 PHP内置web服务器
  19. Lua格式化输出
  20. 计算一元一次方程Y=kX+b

热门文章

  1. maven项目解决pom.xml头部 http://maven.apache.org/xsd/maven-4.0.0.xsd报错的问题
  2. Linux基础教程 linux无密码ssh登录设置
  3. 全方面了解和学习PHP框架PHP培训教程
  4. UINX标准C - 进程管理
  5. UVa 1601 || POJ 3523 The Morning after Halloween (BFS || 双向BFS &amp;&amp; 降维 &amp;&amp; 状压)
  6. 页面禁止刷新处理Js实现
  7. [HDU3072]:Intelligence System(塔尖+贪心)
  8. 关于同时可用git命令clone和TortoiseGit拉取代码不需要密码
  9. Visual Studio 2019 企业版 注册码 百度云下载
  10. legend3---阿里云如何多个域名指向同一个网站