一、題目大意

就是求中間的數。

二、AC code

遞歸快排ac版：

#include <iostream> #include <stdio.h> #include <cstring> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <cassert> #include <time.h> #include <queue> #include <map> #include <stack> #include <bitset> #include <string> #include <sstream> #include <list> #define INF 0x3f3f3f3fusing namespace std;template <class Type> Type stringToNum(const string& str) {istringstream iss(str);Type num;iss >> num;return num; }//======================================================#define MAXN 250002int a[MAXN];void quickSort(int *arr, int left, int right){int i = left, j = right;int mid = arr[(i+j)/2];while(i <= j){while(arr[i] < mid) i ++;while(arr[j] > mid) j --;if(i <= j){int tmp;tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;i ++; j --;}}if(i < right) quickSort(arr,i, right);if(left < j) quickSort(arr,left, j); }int main() {//freopen("input.txt","r",stdin);int N;cin>>N;for (int i = 1; i <= N; ++i) {scanf("%d",&a[i]);}quickSort(a,1,N);if(N%2) //oddprintf("%d.0\n", a[(N+1)/2]);else {double sum = (double)a[N/2] + (double)a[N/2+1];printf("%.1lf\n", sum / 2);}return 0; }

可以水過，但是不知道為什么用g++也會WA，用c++ OK
同時因為數的范圍過大，用計數排序不靠譜。

#include <iostream> #include <stdio.h> #include <cstring> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <cassert> #include <time.h> #include <queue> #include <map> #include <stack> #include <bitset> #include <string> #include <sstream> #define INF 0x3f3f3f3fusing namespace std;template <class Type> Type stringToNum(const string& str) {istringstream iss(str);Type num;iss >> num;return num; }//======================================================#define MAXN 250002long long a[MAXN];int main() {//freopen("input.txt","r",stdin);int N;cin>>N;for (int i = 1; i <= N; ++i) {scanf("%lld",&a[i]);}sort(a+1,a+N+1);//oddif(N%2)printf("%lld.0\n", a[(N+1)/2]);else {//printf("%.1lf\n", ((double)a[N/2]+(double)a[(N/2)+1])/2); //ok//ok // double sum = (double)a[N/2]+(double)a[(N/2)+1]; // printf("%.1lf\n",sum / 2);printf("%.1lf\n", (double)(a[N/2]+a[(N/2)+1])/2);}return 0; }

stl二分會超時：

#include <iostream> #include <stdio.h> #include <cstring> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <cassert> #include <time.h> #include <queue> #include <map> #include <stack> #include <bitset> #include <string> #include <sstream> #include <list> #define INF 0x3f3f3f3fusing namespace std;template <class Type> Type stringToNum(const string& str) {istringstream iss(str);Type num;iss >> num;return num; }//======================================================#define MAXN 250002vector<int > v;//有序數組遞減排列 int binarySearch(vector<int > array,int len,int value){int mid=0;int low=0;int high=len-1;while(low<=high){mid=(low+high)/2;if(array[mid]>value){ //在右半區low=mid+1;continue;}else if(array[mid]<value){ //在左半區high=mid-1;continue;}elsereturn mid; //找到}return low; //insert pos }int main() {//freopen("input.txt","r",stdin);int N;cin>>N;for (int i = 1; i <= N; ++i) {long long tmp;scanf("%lld",&tmp);int pos = binarySearch(v,i-1,tmp);v.insert(v.begin() + pos, tmp);}if(N%2) //oddprintf("%lld.0\n", v[(N+1)/2-1]);elseprintf("%.1lf\n", (double)(v[N/2-1]+v[N/2])/2);return 0; }

總結

以上是生活随笔為你收集整理的poj 2623 快排的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。