首页 > 其他 > 详细

Codeforces Round #315 (Div. 2) 569B Inventory

时间:2015-08-11 22:43:30      阅读:453      评论:0      收藏:0      [点我收藏+]

题目:Click here

题意:给你n,然后n个数,n个数中可能重复,可能不是1到n中的数。然后你用最少的改变数,让这个序列包含1到n所有数,并输出最后的序列。

分析:贪心。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int M = 1e5+5;
 4 
 5 int n;
 6 int a[M];   // 给定序列
 7 int mark[M];    // mark[i] 表示i在给定序列中的出现次数
 8 int notap[M];   // 给的序列中没有出现的元素
 9 bool firstout;
10 
11 void print( int x ) {   // 输出格式控制 ps:在CF上测试了一下,不管这个格式也能AC
12     if( firstout )  {
13         printf("%d", x );
14         firstout = false;
15     }  
16     else
17         printf(" %d", x );
18 }
19 
20 int main()  {
21     while( ~scanf("%d", &n ) )  {
22         memset( mark, 0, sizeof(mark) );
23         memset( notap, 0, sizeof(notap) );
24         for( int i=1; i<=n; i++ )   {
25             scanf("%d", a+i );
26             mark[a[i]]++;
27         }
28         int cnt = 1;
29         for( int i=1; i<=n; i++ )
30             if( !mark[i] )  {
31                 notap[cnt] = i;
32                 cnt++;
33             }
34         firstout = true;
35         int top = 1;
36         for( int i=1; i<=n; i++ )
37             if( mark[a[i]] == 1 && a[i] <= n )  // 给定序列中有这个数并且范围合法
38                 print( a[i] );
39             else    {
40                 print( notap[top] );    // 不然从没有的序列中弹出一个数
41                 top++;
42                 mark[a[i]]--;
43             }
44         printf("\n");
45     }
46     return 0;
47 }

 

Codeforces Round #315 (Div. 2) 569B Inventory

原文:http://www.cnblogs.com/TaoTaoCome/p/4722294.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!