poj 2623 快排

简介:

一、题目大意

就是求中间的数。

二、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;
}
相关文章
|
6月前
|
搜索推荐 算法
AcWing 785. 快速排序(一篇解决快速排序中的边界问题!)
AcWing 785. 快速排序(一篇解决快速排序中的边界问题!)
poj 1990 MooFest 树状数组
题意就是有N头牛,每头牛都有一个坐标和声调值(x, v),两头牛之间通讯要花费的能量是他们的距离乘以最大的一个音调值,现在要任意两头牛之间都相互通讯一次,求总共需要花费多少能量?
45 0
【AcWing】归并排序及其应用
【AcWing】归并排序及其应用
74 0
|
算法 C++
2016年蓝桥杯c/c++ c组第5题 快速排序 双指针
2016年蓝桥杯c/c++ c组第5题 快速排序 双指针
|
人机交互
POJ-2524,Ubiquitous Religions(并查集模板题)
POJ-2524,Ubiquitous Religions(并查集模板题)
|
算法
剑指offer之快速排序
剑指offer之快速排序
160 0