[java]
package D0807;
/*題目大意：給你有幾個文件以及文件碎片現在的位置，要求給出操作方法，
* 使得操作之後文件連續並且緊湊還有總體上文件時按照順序擺放的。
* 例如樣例：20 3 表示20個空間，3個文件4 2 3 11 12
* 第一個文件有4個碎片，分別在2,3,11,121 7 後面的一樣
* 初始目標狀態是：1~4是一號文件的碎片，5號是2號文件的碎片，6~8是3號文件的碎片...總之模擬碎片整理程序。
* 有2種不和諧因素：出現了環，或者鏈。
* 怎麼說呢？環是指一些碎片，上一個碎片占據了下一個碎片應有的位置。然後最後一個占據了第一個位置。
* 而鏈就是最後一個的目標位置是空閒的
* */
import java.util.*;
import java.io.*;
public class POJ1033 {
static int clusters[] = new int[10001];
static int clusters_num, file_num;
static int counter = 1, move_num = 0;//文件片段的真實編號和操作的總數
static int next, i, j, t, n;
static Stack<Integer>s = new Stack<Integer>();
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken();
clusters_num = (int) st.nval;
st.nextToken();
file_num = (int) st.nval;
for (i = 0; i < file_num; i++) {
st.nextToken();
n = (int)st.nval;
for(j = 0;j<n;j++){
st.nextToken();
t = (int)st.nval;
clusters[t] = counter++;
}
}
doit();
out.flush();
}
private static void doit() {
// TODO Auto-generated method stub
for(i = 1;i<=clusters_num;i++){
if(clusters[i]==i)continue;//如果剛好放在了目標位置上就不需要移動。
else if(clusters[i]!=0){//位置上放了文件且位置錯誤
s.push(i);
next = clusters[i];
boolean is_circle = false;
while(true){//判斷是否出現了環
if(clusters[next]==i){
is_circle = true;
break;
}else if(clusters[next]==0){
is_circle = false;
break;
}
s.push(next);
next = clusters[next];
}
if(is_circle){
for(j = clusters_num; j>=0; j--){
if(clusters[j]==0)break;//從後向前找一個空位置，為解開環做准備
}
//System.out.println(next+" "+j);
out.println(next+" "+j);
clusters[j] = clusters[next];
deal();
clusters[next] = clusters[j];//把開始的結點移動回去
clusters[j] = 0;
//System.out.println(j+" "+next);
out.println(j+" "+next);
}else{//沒有環
deal();
clusters[next] = 0;
}
}
}
if(move_num==0)//System.out.println("No optimization needed");
out.println("No optimization needed");
}
private static void deal() {
// TODO Auto-generated method stub
while(!s.isEmpty()){
t = s.peek();
//System.out.println(t+" "+next);
out.println(t+" "+next);
clusters[next] = clusters[t];
next = t;
s.pop();
move_num++;
}
}
作者：lhfight
