"这道题很神奇的贪心，第一章中讲贪心算法时讲过这个题的算法。
其实就是统计出1，2，3的个数，在1的位置上出现的2记为n12，在2位置上出现的1记为n21，如此。如果n12==n21，那么说明这两个位置上的数字只要一次交换就能得到最少的交换次数，如果其中某一个较大，那么较小的那个数就可以通过一次交换得到。其他位置同理。
把可以交换一次得到的个数都在各自中减去，那么剩下的序列必定每3个形如（3，2，1）的序列可以通过两次交换排序好，所以，对剩余的n(i,j)进行求和，再乘以2除以3，得到的数加到sum上即可……"
———–以上引用自Ac的幸福……的blog
需要注意的是当所有数全一样时输出0。我代码写得好像有点复杂了。
My code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | /* ID: tgh7281 LANG: C++ TASK: sort3 */ #include <iostream> #include <fstream> using namespace std; int main() { ifstream fin("sort3.in"); ofstream fout("sort3.out"); int n; int num[1000],a[4]={0}; fin>>n; for (int i=0;i<n;i++) { fin>>num[i]; a[num[i]]++; } int p[4][4]={0}; for (int i=0;i<a[1];i++) { if (num[i]==2) p[1][2]++; else if (num[i]==3) p[1][3]++; } for (int i=a[1];i<a[2]+a[1];i++) { if (num[i]==1) p[2][1]++; else if (num[i]==3) p[2][3]++; } for (int i=a[2]+a[1];i<n;i++) { if (num[i]==2) p[3][2]++; else if (num[i]==1) p[3][1]++; } int res=0,m[4]; m[1] = min(p[1][2],p[2][1]); res += m[1]; p[1][2] -= m[1]; p[2][1] -= m[1]; m[2] = min(p[1][3],p[3][1]); res += m[2]; p[1][3] -= m[2]; p[3][1] -= m[2]; m[3] = min(p[3][2],p[2][3]); res += m[3]; p[3][2] -= m[3]; p[2][3] -= m[3]; m[0] = p[1][2]+p[2][1]+p[1][3]+p[3][1]+p[2][3]+p[3][2]; res += m[0]*2/3; if (m[0]||m[1]||m[2]||m[3]) fout<<res<<endl; else fout<<0<<endl; return 0; } |
981 views