sortingathree-valuedsequence - codetrick
Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.
In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.
You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.
X. Simulation
http://www.boyu0.com/usaco-sorting-three-valued-sequence/
我们只要分别计算出1，2和3的个数，就能够知道最后排序的结果了，排序后第一个1出现的位置肯定是0，第一个2出现的位置为1的个数，第一个3出现的位置是1和2个数的和。。。
那么，我们要使交换的次数最少，我们只要保证当交换时，如果可以使两个交换的数字同时归位，那么就选择这个交换，如果不行，再做其他交换，那么交换的次数肯定就是最少的了。
我们只要通过程序用这个策略去模拟交换，最后统计交换的次数就行了
X. Simulation
http://qingtangpaomian.iteye.com/blog/1635261
http://bywbilly.blog.163.com/blog/static/2027010772012224103921168/
Read full article from sortingathree-valuedsequence - codetrick
Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.
In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.
You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.
PROGRAM NAME: sort3
INPUT FORMAT
| Line 1: | N (1 <= N <= 1000), the number of records to be sorted |
| Lines 2-N+1: | A single integer from the set {1, 2, 3} |
SAMPLE INPUT (file sort3.in)
9 2 2 1 3 3 3 2 3 1
OUTPUT FORMAT
A single line containing the number of exchanges requiredSAMPLE OUTPUT (file sort3.out)
4
给你一个只有1 2 3 的序列,要你排序，每次可以交换任意两个元素，问最小交换次数是多少
思路:贪心，先排1 ,如果1已经在位置上了,那就不要动了,如果是２那就和最前面的１交换,如果是3，那就和后面的１交换
http://www.cs.ru.ac.za/research/g04h2708/USACO-Greedy.html
The sequence has three parts: the part which will be 1 when in sorted order, 2 when in sorted order, and 3 when in sorted order. The greedy algorithm swaps as many as possible of the 1's in the 2 part with 2's in the 1 part, as many as possible 1's in the 3 part with 3's in the 1 part, and 2's in the 3 part with 3's in the 2 part. Once none of these types remains, the remaining elements out of place need to be rotated one way or the other in sets of 3. You can optimally sort these by swapping all the 1's into place and then all the 2's into place.
Analysis: Obviously, a swap can put at most two elements in place, so all the swaps of the first type are optimal. Also, it is clear that they use different types of elements, so there is no ``interference'' between those types. This means the order does not matter. Once those swaps have been performed, the best you can do is two swaps for every three elements not in the correct location, which is what the second part will achieve (for example, all the 1's are put in place but no others; then all that remains are 2's in the 3's place and vice-versa, and which can be swapped).
标程3:
http://lsharemy.com/wordpress/index.php/csit/usaco-prob-sorting-a-three-valued-sequence/
http://blog.csdn.net/zztant/article/details/7823887
https://github.com/TomConerly/Competition-Programming/blob/master/USACO/Chapter2/sort3.javahttp://www.cs.ru.ac.za/research/g04h2708/USACO-Greedy.html
The sequence has three parts: the part which will be 1 when in sorted order, 2 when in sorted order, and 3 when in sorted order. The greedy algorithm swaps as many as possible of the 1's in the 2 part with 2's in the 1 part, as many as possible 1's in the 3 part with 3's in the 1 part, and 2's in the 3 part with 3's in the 2 part. Once none of these types remains, the remaining elements out of place need to be rotated one way or the other in sets of 3. You can optimally sort these by swapping all the 1's into place and then all the 2's into place.
Analysis: Obviously, a swap can put at most two elements in place, so all the swaps of the first type are optimal. Also, it is clear that they use different types of elements, so there is no ``interference'' between those types. This means the order does not matter. Once those swaps have been performed, the best you can do is two swaps for every three elements not in the correct location, which is what the second part will achieve (for example, all the 1's are put in place but no others; then all that remains are 2's in the 3's place and vice-versa, and which can be swapped).
标程3:
http://lsharemy.com/wordpress/index.php/csit/usaco-prob-sorting-a-three-valued-sequence/
int main () { int s[1024]; int n; int sc[4] = {0}; ifstream fin("sort3.in"); ofstream fout("sort3.out"); fin>>n; for (int i = 0; i < n; i++) { fin>>s[i]; sc[s[i]]++; } int s12 = 0, s13 = 0, s21 = 0, s31 = 0, s23 = 0, s32 = 0; for (int i = 0; i < sc[1]; i++){ if (s[i] == 2) s12++; if (s[i] == 3) s13++; } for (int i = sc[1]; i < sc[1]+sc[2]; i++){ if (s[i] == 1) s21++; if (s[i] == 3) s23++; } for (int i = sc[1]+sc[2]; i < sc[1]+sc[2]+sc[3]; i++){ if (s[i] == 1) s31++; if (s[i] == 2) s32++; } fout<<min(s12, s21)+min(s13, s31)+min(s23, s32) + 2*(max(s12, s21) - min(s12, s21))<<endl; return 0;}- for(i=0;i<N;i++)
- {
- fscanf(fin,"%d",&A[i]);
- B[i]=A[i];
- }
- qsort(A,N,sizeof(int),comp); //A已排序
- for(i=0;i<N;i++)
- {
- temp[A[i]][B[i]]++;
- }
- count=fabs(temp[1][2]-temp[2][1])*2+Min(temp[1][2],temp[2][1])+Min(temp[1][3],temp[3][1])+Min(temp[2][3],temp[3][2]);
| ||
| * we want to switch them. So first do all of the moves which corrects 2. | ||
| * The number is min(1in2,2in1)+min(1in3,3in1)+min(2in3,3in2). Note that we | ||
| * have to have exactly k misplaced 1s, k misplaced 2s, and k misplaced 3s | ||
| * (try it out, this has to be true). So this is basically solving something like | ||
| * 312 but 3...31...12...2 which takes 2*k moves. |
X. Simulation
http://www.boyu0.com/usaco-sorting-three-valued-sequence/
我们只要分别计算出1，2和3的个数，就能够知道最后排序的结果了，排序后第一个1出现的位置肯定是0，第一个2出现的位置为1的个数，第一个3出现的位置是1和2个数的和。。。
那么，我们要使交换的次数最少，我们只要保证当交换时，如果可以使两个交换的数字同时归位，那么就选择这个交换，如果不行，再做其他交换，那么交换的次数肯定就是最少的了。
我们只要通过程序用这个策略去模拟交换，最后统计交换的次数就行了
int main()
{
FILE *fin = fopen ("sort3.in", "r");
FILE *fout = fopen ("sort3.out", "w");
int n;
int num[1000];
int bucket[3] = {0};
int i, j;
int start, end;
int ans = 0;
fscanf(fin, "%d", &n);
for (i = 0; i < n; ++i)
{
fscanf(fin, "%d", &num[i]);
++bucket[num[i] - 1];
}
// bucket[i - 1] set to the start position of i when bucket is sorted.
bucket[2] = bucket[1];
bucket[1] = bucket[0];
bucket[2] += bucket[0];
bucket[0] = 0;
// find 1 and change it is position
for (i = 0; i < bucket[1]; ++i)
{
if (num[i] != 1)
{
start = bucket[num[i] - 1];
end = num[i] == 2 ? bucket[2] : n;
for (j = start; j < end; ++j)
{
if (num[j] == 1)
{
num[j] = num[i];
num[i] = 1;
++ans;
break;
}
}
if (j == end)
{
if (num[i] == 2)
{
start = bucket[2];
end = n;
}
else
{
start = bucket[1];
end = bucket[2];
}
for (j = start; j < end; ++j)
{
if (num[j] == 1)
{
num[j] = num[i];
num[i] = 1;
++ans;
break;
}
}
}
}
}
// find 2
for (i = bucket[1]; i < bucket[2]; ++i)
{
if (num[i] == 3)
++ans;
}
fprintf(fout, "%d\n", ans);
return 0;
}
http://my.oschina.net/stormdpzh/blog/49082 for(int i = 0; i < N; i++) { cin >> num[i]; sorted[i] = num[i]; } sort(sorted, sorted + N); memset(toChange, 0, sizeof(int)); for(int i = 0; i < N; i++) { if(sorted[i] == 1 && num[i] == 2) toChange[1][2]++; else if(sorted[i] == 1 && num[i] == 3) toChange[1][3]++; else if(sorted[i] == 2 && num[i] == 1) toChange[2][1]++; else if(sorted[i] == 2 && num[i] == 3) toChange[2][3]++; else if(sorted[i] == 3 && num[i] == 1) toChange[3][1]++; else if(sorted[i] == 3 && num[i] == 2) toChange[3][2]++; } change = 0; int leave = 0; //leave:两两交换之后剩下的 for(int i = 1; i <= 2; i++) { for(int j = 1; j <= 3 - i; j++) { int minn = min(toChange[i][i+j], toChange[i+j][i]); change += minn; toChange[i][j+i] -= minn; toChange[j+i][i] -= minn; leave = leave + toChange[i][j+i] + toChange[j+i][i]; } } change += leave * 2 / 3; cout << change << endl;http://qingtangpaomian.iteye.com/blog/1635261
http://bywbilly.blog.163.com/blog/static/2027010772012224103921168/
- public static void main(String[] args) {
- try {
- // Scanner in = new Scanner(System.in);
- // PrintWriter pw = new PrintWriter(System.out);
- Scanner in = new Scanner(new BufferedReader(new FileReader(
- "sort3.in")));
- PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
- "sort3.out")));
- int num = in.nextInt();
- int cnt = 0;
- int[] input = new int[num];
- int[] sorted = new int[num];
- int[] position = new int[4];
- for (int i=0;i<num;i++){
- int temp = in.nextInt();
- if (temp == 1){
- position[1]++;
- } else if (temp == 2){
- position[2]++;
- } else {
- position[3]++;
- }
- input[i] = temp;
- sorted[i] = temp;
- }
- Arrays.sort(sorted);
- position[3] = position[2] + position[1];
- position[2] = position[1];
- position[1] = 0;
- for (int i=position[1];i<position[2];i++){
- int temp = input[i];
- if (temp == 2){
- for (int j=position[2];j<num;j++){
- if (input[j] == sorted[i]){
- exchange(i, j, input);
- cnt ++;
- break;
- }
- }
- } else if (temp == 3){
- for (int j=num-1;j>=position[2];j--){
- if (input[j] == sorted[i]){
- exchange(i, j, input);
- cnt ++;
- break;
- }
- }
- }
- }
- for (int i=position[2];i<position[3];i++){
- int temp = input[i];
- if (temp == 3){
- for (int j=num-1;j>=position[2];j--){
- if (input[j] == sorted[i]){
- exchange(i, j, input);
- cnt ++;
- break;
- }
- }
- }
- }
- pw.println(cnt);
- pw.close();
- in.close();
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
- public static void exchange(int i,int j,int[] target){
- int temp = target[i];
- target[i] = target[j];
- target[j] = temp;
- }
Read full article from sortingathree-valuedsequence - codetrick
