0001 #include <cstdio>
0002 #include <cstring>
0003 #include <cstdlib>
0004 #include <ctime>
0005 #include "_share/util.h"
0006 #include "_share/rand.h"
0007 #include "UniPrint/print.h"
0008 #include "vector/vector.h"
0009 #include "unionSelect.h"
0010 
0011 #define S1(k)  ((k) < 0 ? INT_MIN : (k) < n1 ? S1[k] : INT_MAX)
0012 #define S2(k)  ((k) < 0 ? INT_MIN : (k) < n2 ? S2[k] : INT_MAX)
0013 
0014 Vector<int> randomSortedVector(Rank n) { //生成长度为n的随机有序向量
0015    Vector<int> A;
0016    for (Rank i = 0; i < n; i++)
0017       A.insert(rand() % 1000); //元素取自[0,10000)
0018    A.sort();
0019    return A;
0020 } //randomSortedVector
0021 
0022 int main(int argc, char* argv[]) { //中位数算法测试
0023    if (3 > argc) { printf("Usage:\n\t%s <n> <tests>\n", argv[0]); return 1; }
0024    Rank N = atoi(argv[1]); //长度上限
0025    Rank T = atoi(argv[2]); //测试轮数
0026    if ((T < 1) || (N < 1)) { printf("arguments error\n"); return 1; }
0027    srand(31415926); //srand((uint32_t) time(nullptr)); //随机种子
0028    int ok = 0;
0029    for (Rank i = 0; i < T; i++) { //反复地
0030       printf("-------- [%d] --------\n", i);
0031       Rank n1 = dice(N) + 1;
0032       Rank n2 = dice(N) + 1;
0033       //if (n1 > n2) swap(n1, n2);
0034       Rank n = n1 + n2;
0035       Vector<int> S1 = randomSortedVector(n1); //PRINT(S1);
0036       Vector<int> S2 = randomSortedVector(n2); //PRINT(S2);
0037       Vector<int> X;
0038       PRINT(S1); PRINT(S2);
0039       for (Rank k = 0; k < n; k++) { //逐项选取
0040          X.insert(unionSelect(S1, S2, k));
0041          //PRINT(X);
0042       }
0043       Vector<int> Y;
0044       for (Rank i1=0, i2=0; (i1<n1) || (i2<n2); )
0045          Y.insert(S1(i1) <= S2(i2) ? S1[i1++] : S2[i2++]);
0046       PRINT(X); PRINT(Y);
0047       Rank diff = 0;
0048       for (Rank k = 0; k < n; k++)
0049          diff += X[k] != Y[k];
0050       if (0 < diff) printf("<-------------\n");
0051       else ok++;
0052    }
0053    printf("%d/%d OK\n", ok, T);
0054    return 0;
0055 }