USACO analysis
肖肖 |
01 Dec 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
题目
给出一个长度为N的乱序数组,要求求出按照题目给出的代码排序的循环次数
分析
因为数组长度为N(N<=10^5^)而题目算法的复杂度是O(N^2^)所以不能直接进行模拟,观察题目排序方法,是一个双向的冒泡排序,每次循环会把一个i之前大于i的数移到i的后方小于i的数移到前方对于每个位置 i ,所以我们可以看在1到i之间有多少个数比当前的i大的数
复杂度
排序耗费的复杂度O(NlogN),然后遍历每个位置进行计算复杂度O(N);
代码
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct number
{
int index;
int data;
};
int N;
int temp[200000];
number num[200000];
bool cmp(number a,number b){
return a.data < b.data;
}
int main(){
FILE *in = fopen("sort.in","r");
FILE *out = fopen("sort.out","w");
fscanf(in,"%d",&N);
int ans = 1;
for(int i = 0; i < N; i++){
fscanf(in,"%d",&num[i].data);
num[i].index = i;
}
sort(num,num+N,cmp);
int count = 0;
for(int i = 0 ; i < N; i++){
if(num[i].index > i) count++;
if(temp[i]) count--;
ans = max(ans,count);
temp[num[i].index] = 1;
}
fprintf(out, "%d",ans);
return 0;
}
