新手天翼
3908 冒泡排序1
题目描述 Description
给定n个正整数的排列：a0,a1,a2,...,an-1，（1<=n<=500000)，求对这个排列进行冒泡排序所需要的交换次数。 比如，原来的排列为： 5，4，6，3，1，2 排序后的排列为： 1，2，3，4，5，6
输入描述 Input Description
第一行输入一个正整数n，
后面行输入从1到n的n个正整数，按随机顺序排列，用空格隔开
输出描述 Output Description
一个正整数，表示冒泡排序的交换次数
样例输入 Sample Input
6
5 4 6 3 1 2
样例输出 Sample Output
12
数据范围及提示 Data Size & Hint
n个正整数的排列指的是从1到n这n个整数的任意一种排列
Time Limit Exceeded:30分
傅文彬的测评结果：
测试点#1 测评结果 : Accepted 时间 : 0ms
测试点#2 测评结果 : Accepted 时间 : 16ms
测试点#3 测评结果 : Time Limit Exceeded 时间 : 1976ms 偷看一下数据
测试点#4 测评结果 : Time Limit Exceeded 时间 : 1984ms 偷看一下数据
测试点#5 测评结果 : Accepted 时间 : 500ms
测试点#6 测评结果 : Time Limit Exceeded 时间 : 1976ms 偷看一下数据
测试点#7 测评结果 : Time Limit Exceeded 时间 : 1988ms 偷看一下数据
测试点#8 测评结果 : Time Limit Exceeded 时间 : 1984ms 偷看一下数据
测试点#9 测评结果 : Time Limit Exceeded 时间 : 1980ms 偷看一下数据
测试点#10 测评结果 : Time Limit Exceeded 时间 : 1992ms 偷看一下数据
我的提交(cpp)：
#include<bits/stdc++.h>
using namespace std;
int n,h[930000],t,sum,flag=1;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>h[i];
for(int i=1; i<=n-1; i++)
{
if(flag==0)break;
flag=0;
for(int j=1; j<=n-i; j++)
{
if(h[j]>h[j+1])
{
t=h[j];
h[j]=h[j+1];
h[j+1]=t;
flag=1;
sum++;
}
}
}
cout<<sum;
return 0;
}
傅文彬在2019-03-07 20:54:05追加了内容
谢谢
傅文彬在2019-03-07 21:04:21追加了内容
赶快回答呀，谢谢
傅文彬在2019-03-10 20:43:03追加了内容
谢谢
初级守护
这道题目如果引申一下应该是求数组中逆序对的个数（逆序对：i>j但ai<aj）.最快的：分思想将序列分成两个子序列，再对两个序列边排序边统计，统计是在排序之前完成的，所以排序并不影响统计个数。至于还要注意两点问题：（1：数组要开得够大，（2：最后的总交换数应该用long long类型，否则会爆的
void worksort(int l,int r)
{
int mid,tmp,i,j;
if(r>l+1)
{
mid=(l+r)/2;
worksort(l,mid-1);
worksort(mid,r);
tmp=l;
for(i=l,j=mid;i<=mid-1 && j<=r;)
{
if(a[i]>a[j])
{
b[tmp++]=a[j++];//快速排序
sum+=mid-i;//统计逆序对个数
}
else
b[tmp++]=a[i++];
}
if(j<=r)
for(;j<=r;j++) b[tmp++]=a[j];
else
for(;i<=mid-1;i++) b[tmp++]=a[i];
for(i=l;i<=r;i++) a[i]=b[i];//将排好序的b数组赋值给a数组
}
else
{
if(l+1==r)//递归的边界
if(a[l]>a[r])
{
swap(a[l],a[r]);
sum++;
}
}
}
这一段是二分的内容，就是找出1~n数组中逆序对的个数，可以看一下，这个效率是稳过的（看懂后自己补充下主程序就好了
速度还可以，最大的点236ms，可以过的（https://blog.csdn.net/qq_39692612/article/details/78254007）
初级守护
#include<bits/stdc++.h>
using namespace std;
long long a[1000000],b[100000];
int main(){
int n,flag=1;
cin>>n;
long long cnt=0,cnt1=0,minn=1000000;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
for(int i=1;i<=n;i++){
flag=0;
for(int j=1;j<=n-i;j++){
if(a[j]>a[j+1]){
flag=1;
int t;
cnt++;
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
if(flag==0){
break;
}
}
for(int i=1;i<=n;i++){
flag=0;
for(int j=1;j<=n-i;j++){
if(b[j]>b[j+1]){
flag=1;
int t;
cnt1++;
t=b[j];
b[j]=b[j+1];
b[j+1]=t;
}
}
if(flag==0){
break;
}
}
minn=min(cnt,cnt1);
cout<<minn;
return 0;
}
三十
修练者
降时间复杂度
中级光能
for循环有问题
修练者
int a,s=0,f=0;
cin>>a;
for(int i=1;i<=a;i++)
{
if(i%7==0)
{
f++;
s+=i;
}
}
cout<<f<<endl<<s;
核心代码送给你
新手守护
你这个超时了，优化一下
新手天翼
你好啊
初级守护
呃呃呃，你可以试一下其他算法，冒泡本来就很慢
修练者
#include<iostream>
using namespace std;
int a[500001];
int main()
{
int n,s=0,t=0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n-1;i++)
{
for(int j=1;j<=n-i;j++)
{
if(a[j]>a[j+1])
{swap(a[j],a[j+1]);s++;}
}
}
cout<<s;
return 0;
}
30fen
修练者
你不会优化吗
