程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> soj3102 O（n）求第k小的數

soj3102 O（n）求第k小的數

編輯：C++入門知識

soj3102 O（n）求第k小的數

原本覺得挺簡單的，開始就一直RE，後來還T。。發現是服務器可能出問題了，老化了，時間變慢了，拿以前A掉的代碼來都是T。

不過還是有快的方法的。

就是位運算。另外stl裡也有現成的函數可以用nth_element(s,s+k-1,s+n);

但是還有一個問題，nth_element()換成自己寫的就T。。無語了。。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define read freopen(q.in,r,stdin)
#define write freopen(q.out,w,stdout)
using namespace std;
int x[2000006],f[2000];
char s[22000006];
int n,k;


int main()
{
   // read;
    memset(f,0,sizeof(f));
    for(int i='0';i<='9';i++)f[i]=1;
    while(~scanf(%d%d,&n,&k))
    {
        getchar();
        int i,j=0,cnt=0;
        memset(x,0,sizeof(x));
        gets(s);
        int len=strlen(s);
        int cur=0;
        for(i=cur=0;i

貼上T的代碼 
 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define read freopen(q.in,r,stdin)
#define write freopen(q.out,w,stdout)
using namespace std;
int x[2000006],f[2000];
char s[22000006];
int n,k;

int findKth(int left,int right)
{
   // if(left==right)return left; 
    int i=left,j=right,center,tmp;
    int p=right;
    center=x[p];
    for(;i=center && ii)return find(i+1,r);
    else return find(l,i-1);
}


int main()
{
    //read;
    memset(f,0,sizeof(f));
    for(int i='0';i<='9';i++)f[i]=1;
    while(~scanf(%d%d,&n,&k))
    {
        getchar();
        int i,j=0,cnt=0;
        memset(x,0,sizeof(x));
        gets(s);
        int len=strlen(s);
        int cur=1;
        for(i=0;i