POJ 2299题解

题解"/>

POJ 2299题解

没什么卵用的目录

• 原题地址
• AC代码
• 题解和题目思路

原题地址

这是地址

AC代码

#include <iostream>
#include <algorithm>using namespace std;long long int merge(long long int *list,long long int op,long long int ed){if(op==ed)return 0;long long int counter =0;counter+=merge(list,op,(op+ed)/2);counter+=merge(list,(op+ed)/2+1,ed);long long int x[ed-op+1];long long int i,j,it;i=op;j=(op+ed)/2+1;it = 0;while(i!=(op+ed)/2+1&&j!=ed+1){if(list[i]<=list[j]){x[it]=list[i];i++;}else{counter+=(op+ed)/2-i+1;x[it]=list[j];j++;}it++;}while(i!=(op+ed)/2+1){x[it]=list[i];i++;it++;}while(j!=ed+1){x[it]=list[j];j++;it++;}for (long long int k = op; k <=ed ; ++k) {list[k]=x[k-op];}return counter;
}int main() {ios::sync_with_stdio(false);long long int n;while(cin>>n,n!=0){long long int counter = 0,list[n];for (long long int i = 0; i < n; ++i) {cin>>list[i];}counter = merge(list,0,n-1);cout<<counter<<endl;}return 0;
}

题解和题目思路

这道题原本我还想故技重施1804的套路的，结果大失败，TLE，O(N²)不行，冒泡只会比这个更慢，那我们就只能请出来高级冒泡：Merge了。然后剩下的你们就去找Merge的实现原理好了（滑稽）记得统计交换的次数