ZOJ 3365 Integer Numbers
Integer Numbers
This problem will be judged on ZJU. Original ID: 3365
64-bit integer IO format: %lld Java class name: Main
The boy likes numbers. He has a sheet of paper. He have written a sequence of consecutive integer numbers on the sheet. The boy likes them.
But then the girl came. The girl is cruel. She changed some of the numbers.
The boy is disappointed. He cries. He does not like all these random numbers. He likes consecutive numbers. He really likes them. But his numbers are not consecutive any more. The boy is disappointed. He cries.
Help the boy. He can change some numbers. He would not like to change many of them. He would like to change as few as possible. He cannot change their order. He would like the numbers to be consecutive again. Help the boy.
Input
The first line of the input file contains n --- the number of numbers in the sequence (1 ≤ n ≤ 50000). The next line contains the sequence itself --- integer numbers not exceeding 109 by their absolute values.
There are multiple cases. Process to the end of file.
Output
Output the minimal number of numbers that the boy must change. After that output the sequence after the change.
Sample Input
6
5 4 5 2 1 8
Sample Output
3
3 4 5 6 7 8
Source
Author
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define pii pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = ;
vector<int>g[maxn];
int lisan[maxn],d[maxn],n;
int main() {
while(~scanf("%d",&n)){
for(int i = ; i < n; ++i){
g[i].clear();
scanf("%d",d+i);
lisan[i] = d[i] - i;
}
sort(lisan,lisan+n);
int cnt = ;
for(int i = ; i < n; ++i)
if(lisan[cnt-] != lisan[i]) lisan[cnt++] = lisan[i];
for(int i = ; i < n; ++i){
int index = lower_bound(lisan,lisan+cnt,d[i]-i)-lisan;
g[index].push_back(i);
}
int idx = -,mx = ;
for(int i = ; i < cnt; ++i)
if(g[i].size() > mx) mx = g[idx = i].size();
printf("%d\n",n - g[idx].size());
int tmp = g[idx][];
tmp = d[tmp] - tmp;
for(int i = ; i < n; ++i)
printf("%d%c",tmp + i,i+ == n?'\n':' ');
}
return ;
}
最新文章
- linux 系统工具集
- Install CentOS 7 on Thinkpad t430
- poj2676 Sudoku(DFS)
- Nginx禁止通过IP,未绑定域名访问服务器
- TPL(Task Parallel Library)多线程、并发功能
- java利用反射调用类的某个方法
- idea maven 无法加载已经安装的模块
- 轻量级代码生成器-OnlyCoder
- 解析spring循环依赖策略
- npm lodash
- ibatis项目应用
- requests库入门02-简单了解HTTP协议
- Unity项目中文字的统一管理
- dmi-ipmi
- 操作Linux系统环境变量的几种方法
- Mybatis进阶学习笔记——动态代理方式开发Dao接口、Dao层(推荐第二种)
- django高并发优化
- PHP守护进程化
- 使用CefSharp在.Net程序中嵌入Chrome浏览器(三)——基本操作
- ElasticStack系列之十六 &; ElasticSearch5.x index/create 和 update 源码分析