苹果与橙子
问题提出
有两种不同的水果，排成一排，苹果（1） 和橙子（0）， 问最少需要交换多少次，使得苹果们排在一起，橙子们排在一起。
让这一排先是所有的苹果接着是所有的橙子。
解题思路
这道题如果用选择排序会很不方便,我们可以换一种思路
- 统计有多少个0
- 统计有多少个1
- sx=求
应该是1的部分有多少个0 - sy=求
应该是0的部分有多少个1 - output min(sx,sy);
代码
#include<iostream>
using namespace std;
int a[1001];
void myin(int n) {
for (int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
}
void myout(int n) {
for (int i = 1; i <= n; i++){
printf("%d ", a[i]);
}
printf("\n");
}
int main() {
int n;
cin >> n;
int c0 = 0, c1 = 0;
myin(n);
for (int i = 1; i <= n; i++){
a[i]==0?c0++:c1++;
}
int sx = 0, sy = 0;
for (int i = 1; i <= c1; i++){
if (a[i] == 0){
sx++;
}
}
for (int i = c1 + 1; i <= n; i++){ //注意，i的初值是c1+1而不是1
if (a[i] == 1){
sy++;
}
}
printf("%d", sx<sy?sx:sy);
return 0;
}