C++ 怎么样打乱一个数组顺序,然后复原为原来的值

C++语言 码拜 9年前 (2016-06-09) 2220次浏览
给出一个长度为N的序列A1,A2,…..,AN,其中每项都是小于10^5的自然数。
现在有m个询问,每个询问都是Ai,…,Aj中第k小的数等于多少?
第一行两个正整数n,m。 0<=n<=10000;  0<=m<=2000;
第二行n个数,表示序列A1,A2,…..,AN。
紧接着m行,每行三个正整数i,j,k,(k<=j-i+1),表示询问Ai…Aj中第k小的数等于多少。
m行,第i行为第i次查询的结果。
解决方案

5

取第k小不需要排序有O(N)的算法

5

区间第k大数用划分树可以做,好像主席树也可以

30

仅供参考:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int d[6];
int i,n,a,b,t;
int c,j;
void main() {
    srand(time(NULL));
    printf("shuffle 0..n-1 demo\n");
    for (n=1;n<=5;n++) {/* 测试1~5个元素 */
        printf("_____n=%d_____\n",n);
        j=1;
        for (c=1;c<=n;c++) j=j*c;/* j为n! */
        j*=n*2;
        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */
            for (i=0;i<n;i++) d[i]=i;/* 填写0~n-1 */
            for (i=n;i>0;i--) {/* 打乱0~n-1 */
                a=i-1;b=rand()%i;
                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
            }
            printf("%04d:",c);
            for (i=0;i<n;i++) printf("%d",d[i]);
            printf("\n");
        }
    }
    printf("shuffle 1..n demo\n");
    for (n=1;n<=5;n++) {/* 测试1~5个元素 */
        printf("_____n=%d_____\n",n);
        j=1;
        for (c=1;c<=n;c++) j=j*c;/* j为n! */
        j*=n*2;
        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */
            for (i=1;i<=n;i++) d[i]=i;/* 填写1~n */
            for (i=n;i>1;i--) {/* 打乱1~n */
                a=i;b=rand()%i+1;
                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
            }
            printf("%04d:",c);
            for (i=1;i<=n;i++) printf("%d",d[i]);
            printf("\n");
        }
    }
}

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明C++ 怎么样打乱一个数组顺序,然后复原为原来的值
喜欢 (0)
[1034331897@qq.com]
分享 (0)