P1327 数列排序

一，手动模拟

拿过一个题来先人工模拟一下，发现用模拟的方法可以解出来，现在用编程实现模拟就可以了

二，框架

使用结构体存储数值和一开始的位置
做一个源数据的副本，然后按照数值大小从大到小排序一遍（带编号）
比较排序好的sorted[i].data和原来的in[i]作比较

　　如果值相等说明不必交换，直接跳过，++i
如果值不相等说明需要交换，把原数据和排好序的数交换，++ans

下一个直到结束，输出ans

三，细节

框架第2步的排序使用快排
3.2这一步里，交换并不是真的把源数据里的in[i]和sorted[i].data一样的值交换，因为这样查找sorted[i].data还是需要遍历一遍，所以通过二分查找orted[i].data（已经有序）并修改其位置sorted[i].site就可以了

四，总结

模拟题锻炼了一个复杂的模拟题按顺序解出来的能力

五，代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstdlib>
 5 using namespace std;
 6 pair <int,int> px[100001];
 7 int n;
 8 int in[100001];
 9 int ans;
10 bool cmp(pair <int,int> a,pair <int,int> b)
11 {
12     return a.first < b.first;
13 }
14 inline int finds(int l, int r, int key)
15 {
16     int mid;
17     while(l <= r)
18     {
19         mid = (l + r) / 2;
20         if(px[mid].first == key)
21             return mid;
22         else
23         if(px[mid].first > key)
24             r = mid - 1;
25         else
26             l = mid + 1;
27     }
28     return -1;
29 }
30 inline int finds2(int l, int r, int key)
31 {
32     for(int k=l;k<=r;++k)
33     {
34         if(px[k].first == key)
35             return k;
36     }
37     return -1;
38 }
39 int main()
40 {
41     cin>>n;
42     for(int i=1;i<=n;++i)
43     {
44         cin>>in[i];
45         px[i].first=in[i];
46         px[i].second=i;
47     }
48     sort(px+1,px+1+n,cmp);
49 
50     for(int i=1;i<=n;++i)
51     {
52         if(px[i].first!=in[i])
53         {
54             ++ans;
55             in[px[i].second]=in[i];
56             int site=-1;//find:in[i]'s site
57             site=finds(i,n,in[i]);
58             px[site].second=px[i].second;
59         }
60         
61     }
62     cout<<ans<<endl;
63     return 0;
64 }