Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:这题还是挺简单的,刚开始还忘了"No optimization needed。。。。囧死了

Posted by zzshigan at 2013-10-31 15:10:53 on Problem 1033
In Reply To:这题还是挺简单的,刚开始还忘了"No optimization needed。。。。囧死了 Posted by:bryanfury at 2009-04-16 19:55:06
这个代码虽然ac,但是貌似这组测试数据通不过。数据如下:

7 2
3 6 3 1
3 5 7 8

正确output:
3 2
1 3
5 4
7 5
6 1
8 6



> 我现在还是菜。。。贴个代码上来吧
> #include <iostream>
> #include <stdio.h>
> #include <stack>
> 
> using namespace std;
> /*
> #include <fstream>
> 
> fstream fin ("input.txt",ios::in);
> 
> #define cin fin
> 
> //*/
> int t;
> int f2[10001];
> int N;
> int K;
> int temp;
> int idx;
> int counter ;
> stack<int> st;
> bool needed = 0;
> 
> int main () {
> 	memset(f2, 0, sizeof(f2));
> 	scanf("%d%d",&N,&K);
> 	
> 	counter = 0;
> 	idx = 0;
> 	for (int i = 1; i <= K; i++) {
> 		scanf("%d", &temp);
> 		for (int j = 1; j <= temp; j++) {
> 			 counter++;		
> 			 scanf("%d", &t);
> 			 f2[t] = counter;
> 		}
> 	}
> 	
> 	for (int i = 1; i <= N; i++) {
> 		if (f2[i]!=0 && f2[i]!=i) {
> 			st.push(i);
> 			idx = f2[i];
> 			while (f2[idx] != 0 && idx != i) {
> 				st.push(idx);
> 				idx = f2[idx];
> 			}
> 			if (f2[idx] == 0) {
> 				while (!st.empty()) {
> 					temp = st.top();
> 					f2[f2[temp]] = f2[temp];
> 					printf("%d%c%d", temp, ' ', f2[temp]);
> 					printf("\n");
> 					needed = 1;
> 					st.pop();
> 				}
> 				f2[i] = 0;
> 			}
> 			else if (idx == i) {
> 				int free;
> 				int x;
> 				for (x = N; f2[x]!=0; x--){}
> 				free = x;
> 				temp = st.top();
> 				printf("%d%c%d", temp, ' ', free);
> 				printf("\n");
> 				needed = 1;
> 				st.pop();
> 				while (!st.empty()) {
> 					temp = st.top();
> 					f2[f2[temp]] = f2[temp];
> 					printf("%d%c%d", temp, ' ', f2[temp]);
> 					printf("\n");
> 					needed = 1;
> 					st.pop();
> 				}
> 				f2[i] = i;
> 				printf("%d%c%d", free, ' ', i);
> 				printf("\n");
> 				needed = 1;
> 			}
> 		}
> 		
> 	}
> 	if (needed == 0) printf("No optimization needed\n");
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator