一、题目大意
就是求中间的数。
二、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 0x3f3f3f3f
using namespace std;
template <class Type>
Type stringToNum(const string& str)
{
istringstream iss(str);
Type num;
iss >> num;
return num;
}
//======================================================
#define MAXN 250002
int 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) //odd
printf("%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 0x3f3f3f3f
using namespace std;
template <class Type>
Type stringToNum(const string& str)
{
istringstream iss(str);
Type num;
iss >> num;
return num;
}
//======================================================
#define MAXN 250002
long 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);
//odd
if(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 0x3f3f3f3f
using namespace std;
template <class Type>
Type stringToNum(const string& str)
{
istringstream iss(str);
Type num;
iss >> num;
return num;
}
//======================================================
#define MAXN 250002
vector<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;
}else
return 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) //odd
printf("%lld.0\n", v[(N+1)/2-1]);
else
printf("%.1lf\n", (double)(v[N/2-1]+v[N/2])/2);
return 0;
}