//WA 了3次才AC,题目不难,但交的人不多,思想很简单,直接见代码 #include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <functional> #include <map> using namespace std; int main() { freopen("in.txt","r",stdin); vector<int> iv_s,//cluster sourse iv_d;//cluster destination int N,K; // 1 <= K < N <= 10000 int si,clu; int sum = 0; cin>>N>>K; char* flg = new char[N+2]; memset(flg,'0',N+2); flg[N+1] = '\0'; int index = 1; bool bval = true; while(K--) { cin>>si; while(si--) { cin>>clu; if(clu != index)//本来就在期望位置的就不需要加入移动簇表中了 { bval = false; iv_s.push_back(clu); iv_d.push_back(index); } flg[clu]='1'; ++index; } } sum = index-1; if(bval == true) { cout<<"No optimization needed"; return 0; } //cout<<&flg[1]<<endl; //cout<<"sum = "<<sum<<endl; //copy(iv_s.begin(),iv_s.end(),ostream_iterator<int>(cout," ")); //cout<<endl; //copy(iv_d.begin(),iv_d.end(),ostream_iterator<int>(cout," ")); //cout<<endl<<endl; { int step = 0; int i = 0; while(iv_s.size() > 0) { bool bval = false; for(i = 0; i < iv_s.size();) { if(flg[ iv_d[i] ] == '0') { cout<<iv_s[i]<<" "<<iv_d[i]<<endl; flg[ iv_d[i] ] = '1'; flg[ iv_s[i] ] = '0'; bval = true; iv_d.erase(iv_d.begin()+i);//迭代器的使用 iv_s.erase(iv_s.begin()+i);//找到自己的位置后,从簇表中删除 ++step; } else ++i; } if(bval == false)//存在死链,必须依赖空闲块进行交换 { for(int i = 1; i <= N; i++) if(flg[i] == '0')//找到一个空闲块 { cout<<iv_s[0]<<" "<<i<<endl; flg[ iv_s[0] ] = '0'; iv_s[0] = i; flg[i] = '1'; ++step; break; } } } // cout<<endl<<"step = "<<step<<endl; } return 1; }
测试数据:
20 3
4 2 3 11 12
1 7
3 18 5 10
8 3
3 3 4 5
3 1 2 7
1 8
6 1
3 6 3 1
4 1
3 3 2 4
8 3
3 1 2 3
3 4 5 6
1 7