|
大小: 1126
备注:
|
← 于2008-02-23 15:36:32修订的的版本6 ⇥
大小: 2172
备注: converted to 1.6 markup
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 1: | 行号 1: |
| ## page was renamed from 程序设计练习26——zju2481——Unique Ascending Array | |
| 行号 2: | 行号 3: |
| http://acm.zju.edu.cn/show_problem.php?pid=2481 |
|
| 行号 38: | 行号 41: |
| http://acm.zju.edu.cn/show_problem.php?pid=2481 | ----- {{{#!cplusplus /*written by proby*/ #include <iostream> #include <list> using namespace std; void Add(list<int>& objList, int i){ list<int>::iterator objIter; for(objIter=objList.begin(); ; objIter++){ if(objIter==objList.end() || *objIter>i){ objList.insert(objIter, i); return; } if(*objIter==i){ return; } } } void MyPrint(list<int>& objList){ list<int>::iterator objIter; list<int>::iterator nextIter; nextIter=objList.begin(); nextIter++; for(objIter=objList.begin(); objIter!=objList.end(); objIter++){ cout<<(*objIter); if( nextIter!=objList.end() ){ cout<<" "; } nextIter++; } cout<<endl; } int main(){ list<int> objList; list<int>::iterator listIter; int nLen, objInt, i; cin>>nLen; while(nLen!=0){ for(i=0; i<nLen; i++){ cin>>objInt; Add(objList, objInt); } MyPrint(objList); objList.clear(); cin>>nLen; } return 1; } }}} |
Unique Ascending Array
http://acm.zju.edu.cn/show_problem.php?pid=2481
Time limit: 1 Seconds
Memory limit: 32768K
Given an array of integers A[N], you are asked to decide the shortest array of integers B[M], such that the following two conditions hold.
For all integers 0 <= i < N, there exists an integer 0 <= j < M, such that A[i] == B[j]
For all integers 0 =< i < j < M, we have B[i] < B[j]
Notice that for each array A[] a unique array B[] exists.
1. Input
The input consists of several test cases. For each test case, an integer N (1 <= N <= 100) is given, followed by N integers A[0], A[1], ..., A[N - 1] in a line. A line containing only a zero indicates the end of input.
2. Output
For each test case in the input, output the array B in one line. There should be exactly one space between the numbers, and there should be no initial or trailing spaces.
3. Sample Input
8 1 2 3 4 5 6 7 8 8 8 7 6 5 4 3 2 1 8 1 3 2 3 1 2 3 1 0
4. Sample Output
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3
1 /*written by proby*/
2 #include <iostream>
3 #include <list>
4 using namespace std;
5
6 void Add(list<int>& objList, int i){
7 list<int>::iterator objIter;
8 for(objIter=objList.begin(); ; objIter++){
9 if(objIter==objList.end() || *objIter>i){
10 objList.insert(objIter, i);
11 return;
12 }
13 if(*objIter==i){
14 return;
15 }
16 }
17 }
18
19 void MyPrint(list<int>& objList){
20 list<int>::iterator objIter;
21 list<int>::iterator nextIter;
22 nextIter=objList.begin();
23 nextIter++;
24 for(objIter=objList.begin(); objIter!=objList.end(); objIter++){
25 cout<<(*objIter);
26 if( nextIter!=objList.end() ){
27 cout<<" ";
28 }
29 nextIter++;
30 }
31 cout<<endl;
32 }
33
34 int main(){
35 list<int> objList;
36 list<int>::iterator listIter;
37 int nLen, objInt, i;
38 cin>>nLen;
39 while(nLen!=0){
40 for(i=0; i<nLen; i++){
41 cin>>objInt;
42 Add(objList, objInt);
43 }
44 MyPrint(objList);
45 objList.clear();
46 cin>>nLen;
47 }
48
49 return 1;
50 }