对于输入序列 9 1 0 5 4
,超快速排序生成输出 0 1 4 5 9
。
您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。
输入格式
输入包括一些测试用例。
每个测试用例的第一行输入整数 n,代表该用例中输入序列的长度。
接下来 n 行每行输入一个整数 ai,代表用例中输入序列的具体数据,第 i行的数据代表序列中第 i个数。当输入用例中包含的输入序列长度为 0 时,输入终止,该序列无需处理。
输出格式
对于每个需要处理的输入序列,输出一个整数 op,代表对给定输入序列进行排序所需的最小交换操作数,每个整数占一行。
数据范围
0≤n<5000000
一个测试点中,所有 n的和不超过 500000
0≤ai≤999999999
输入样例:
5
9
1
0
5
4
3
1
2
3
0
输出样例:
6
0
分析:
while(cin>>n&&n){//如果这里“&&”用“,”会超时
for(int i=1;i<=n;i++) cin>>a[i];
cout<<merge_sort(1,n)<<endl;
}
在这段代码中,while(cin>>n&&n)
是一个循环的条件,它包含两个主要的条件:
-
cin >> n
:这个表达式从标准输入(通常是键盘)读取一个整数,并尝试将它赋值给变量n
。如果读取成功,这个表达式的结果是输入流对象cin
,它会在布尔上下文中被解释为true
。如果读取失败(例如,因为输入结束或者输入的不是一个整数),这个表达式的结果是false
,循环将终止。 -
n
:这个条件检查变量n
是否非零。在布尔上下文中,非零值被解释为true
,零值被解释为false
。因此,如果n
是零,循环将终止。
这两个条件用 &&
(逻辑与)连接,意味着只有当两个条件都为 true
时,整个条件才为 true
,循环才会继续。
现在,如果你把 &&
替换为 ,
(逗号),这两个条件将不再被逻辑与连接。在 C++ 中,逗号运算符 ,
会计算其左侧的操作数,丢弃其结果,然后计算其右侧的操作数,并返回右侧操作数的结果。因此,条件 cin >> n, n
将实际上只检查 n
是否非零。即使 cin >> n
失败(例如,因为输入结束),循环仍会继续执行,因为逗号运算符不会考虑 cin >> n
的结果。
#include<iostream>
#define N 500010
using namespace std;
int a[N];
long long merge_sort(int l,int r){
int p[N];//记排序后的数列
if(l>=r) return 0;
int mid=(l+r)>>1;
long long res=merge_sort(l,mid)+merge_sort(mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(a[i]<a[j]){
p[k++]=a[i++];
}
else{
p[k++]=a[j++];
res+=mid-i+1;
}
}
while(i<=mid) p[k++]=a[i++];
while(j<=r) p[k++]=a[j++];
for(i=l,j=0;j<k;i++,j++){
a[i]=p[j];
}
return res;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
while(cin>>n&&n){//如果这里“&&”用“,”会超时
for(int i=1;i<=n;i++) cin>>a[i];
cout<<merge_sort(1,n)<<endl;
}
return 0;
}