【OJ】正整数连接的最小值

喜欢ヅ旅行 2024-04-19 15:43 51阅读 0赞

### 题目描述 ###

题目1中，将1mm厚的纸对折39次，厚度竟然能达到地球到月球的距离，不仅让我们对2的n次方刮目相看，就好象是“指数爆炸”，反复翻倍几次数值就骤然增长。所以我们在解题时务必要注意问题中是否涉及指数爆炸。否则即使费力写出了程序，可能得运行几千年才能得出结果。  
　　另一方面，若将指数爆炸为我所用，它就能成为解决问题的有力武器。二分法查找就是利用了指数爆炸来对大量数据信息进行高速查找的算法。指数爆炸在现代密码技术也起到了关键性作用。例如，4位二进制密码，暴力枚举的话，最多试16次就能破解了。而密码位数每增加1位，暴力枚举的次数就翻一倍。  
　　算一算，如果密码有512位的话，密钥的总数＝2512＝  
　　　13407807929942597099574024998205846127479365820592  
　　　39337772356144372176403007354697680187429816690342  
　　　76900318581864860508537538828119465699464336490060  
　　　84096  
此时，要想暴力破解的难度就太大了。  
　　在第10章大家学习了很多排序方法。其中一些简单的排序算法，其时间复杂度为O(n2)，而快速排序、堆排序、归并排序的时间复杂度优化到了O(n\*log2n)，可别小看了这n－>log2n的优化。从问题1我们已经体验到了，再庞大的数，其对数也将相对很小。  
　　说这么多，无非就是让大家感受时间复杂度的重要性，既然我们说到这了，下面这个题，就请大家注意在选择排序算法时，注意n－>log2n的优化。  
　　设有n个正整数，将它们联接成一排，组成一个最小的多位整数。例如，3个整数32，3，21连接成的最小整数为：21323。限定n个正整数的取值为１至999之间的正整数。

### 输入 ###

先输入正整数个数n的值（1<=n<=500000）；  
然后输入n个正整数（取值范围为1~999）。

### 输出 ###

输出n个正整数连接而成的最小整数。

### 样例输入 ###

7
    3 32 33 34 323 333 343

### 样例输出 ###

3232333333334334

### 提示 ###

本题可以利用排序算法解决，只是排序时要注意一些特殊情况的处理。比如：3　32　34连接成的最小整数为32334

又如：3　32　322　324连接成的最小整数为322323243

注意：本题限定空间为6MB，请注意空间复杂度；限定时间为2秒，更要注意时间复杂度。具体来说，基本上只让大家开全局数组int a\[500000\]，并限制大家使用时间复杂度为O(n\*n)的算法，即最好采用快速排序、堆排序等算法。

### 解题代码 ###

基本思路：  
首先需要读懂题目的排序规则，这个规则很明显与一般的排序大不相同。  
比如说： 322 32 两个数进行连接，可以是32322，也可以是32232，这里面有个规则，总而言之就是要使得连接后的数小即可。  
所以考虑编写一个函数，专门针对这种情况进行排序，使用C++自带的快速排序函数。  
代码如下：

#include <iostream>
    #include <cmath>
    #include<algorithm>
    using namespace std;
    
    
    int length(int x)
    { 
        int i=0;
        while(x)
        { 
            x /= 10;
            i++;
        }
        return i;
    }
    
    /** * m<n 是否成立 * 32 < 3 * 34 > 3 */
    bool smaller(int m, int n)
    { 
    	// 首先进行两次连接，返回连接后的比较结果
        int length1 = length(m);
        int length2 = length(n);
        int x = m*pow(10,length2) + n;
        int y = n*pow(10,length1) + m;
        return x < y;
    }
    
    int ary[500003];
    
    // written by Smileyan
    int main()
    { 
        int n,i;
        while(cin>>n)
        { 
            for(i=0; i<n; i++)
            { 
                cin>>ary[i];
                // 当我们需要输出排序规则时，则去掉上面一行代码，去掉下一行代码的注释符
                // ary[i] = i+1;
            }
    
            sort(ary,ary+n,smaller);
            for(i=0; i<n; i++)
            { 
                cout<<ary[i]<<",";
            }
            cout<<endl;
        }
        return 0;
    }

【重要补充】  
提交后提示说时间超限……所以我们不得不再次优化一下，但是我保留了上面的代码是有目的的，我们可以事先把这个优先级顺序打印出来，因为题目中明确规定了数据的取值范围\[1,999\] 。所以这999个整数它们的排序是有优先级别选择的。

所以我们不妨在上面代码的基础上，直接打印出\[1,999\]的优先级顺序，然后用户输入的内容就根据这个优先级顺序进行输出即可。

输出排序规则如下：

1000,100,10,101,102,103,104,105,106,107,108,109,110,1,111,11,112,113,114,115,116,117,118,119,120,121,12,122,123,124,125,126,127,128,129,130,131,13,132,133,134,135,136,137,138,139,140,141,14,142,143,144,145,146,147,148,149,150,151,15,152,153,154,155,156,157,158,159,160,161,16,162,163,164,165,166,167,168,169,170,171,17,172,173,174,175,176,177,178,179,180,181,18,182,183,184,185,186,187,188,189,190,191,19,192,193,194,195,196,197,198,199,200,201,20,202,203,204,205,206,207,208,209,210,211,21,212,213,214,215,216,217,218,219,220,221,222,2,22,223,224,225,226,227,228,229,230,231,232,23,233,234,235,236,237,238,239,240,241,242,24,243,244,245,246,247,248,249,250,251,252,25,253,254,255,256,257,258,259,260,261,262,26,263,264,265,266,267,268,269,270,271,272,27,273,274,275,276,277,278,279,280,281,282,28,283,284,285,286,287,288,289,290,291,292,29,293,294,295,296,297,298,299,300,301,302,30,303,304,305,306,307,308,309,310,311,312,31,313,314,315,316,317,318,319,320,321,322,32,323,324,325,326,327,328,329,330,331,332,333,3,33,334,335,336,337,338,339,340,341,342,343,34,344,345,346,347,348,349,350,351,352,353,35,354,355,356,357,358,359,360,361,362,363,36,364,365,366,367,368,369,370,371,372,373,37,374,375,376,377,378,379,380,381,382,383,38,384,385,386,387,388,389,390,391,392,393,39,394,395,396,397,398,399,400,401,402,403,40,404,405,406,407,408,409,410,411,412,413,41,414,415,416,417,418,419,420,421,422,423,42,424,425,426,427,428,429,430,431,432,433,43,434,435,436,437,438,439,440,441,442,443,444,4,44,445,446,447,448,449,450,451,452,453,454,45,455,456,457,458,459,460,461,462,463,464,46,465,466,467,468,469,470,471,472,473,474,47,475,476,477,478,479,480,481,482,483,484,48,485,486,487,488,489,490,491,492,493,494,49,495,496,497,498,499,500,501,502,503,504,50,505,506,507,508,509,510,511,512,513,514,51,515,516,517,518,519,520,521,522,523,524,52,525,526,527,528,529,530,531,532,533,534,53,535,536,537,538,539,540,541,542,543,544,54,545,546,547,548,549,550,551,552,553,554,555,5,55,556,557,558,559,560,561,562,563,564,565,56,566,567,568,569,570,571,572,573,574,575,57,576,577,578,579,580,581,582,583,584,585,58,586,587,588,589,590,591,592,593,594,595,59,596,597,598,599,600,601,602,603,604,605,60,606,607,608,609,610,611,612,613,614,615,61,616,617,618,619,620,621,622,623,624,625,62,626,627,628,629,630,631,632,633,634,635,63,636,637,638,639,640,641,642,643,644,645,64,646,647,648,649,650,651,652,653,654,655,65,656,657,658,659,660,661,662,663,664,665,666,6,66,667,668,669,670,671,672,673,674,675,676,67,677,678,679,680,681,682,683,684,685,686,68,687,688,689,690,691,692,693,694,695,696,69,697,698,699,700,701,702,703,704,705,706,70,707,708,709,710,711,712,713,714,715,716,71,717,718,719,720,721,722,723,724,725,726,72,727,728,729,730,731,732,733,734,735,736,73,737,738,739,740,741,742,743,744,745,746,74,747,748,749,750,751,752,753,754,755,756,75,757,758,759,760,761,762,763,764,765,766,76,767,768,769,770,771,772,773,774,775,776,777,7,77,778,779,780,781,782,783,784,785,786,787,78,788,789,790,791,792,793,794,795,796,797,79,798,799,800,801,802,803,804,805,806,807,80,808,809,810,811,812,813,814,815,816,817,81,818,819,820,821,822,823,824,825,826,827,82,828,829,830,831,832,833,834,835,836,837,83,838,839,840,841,842,843,844,845,846,847,84,848,849,850,851,852,853,854,855,856,857,85,858,859,860,861,862,863,864,865,866,867,86,868,869,870,871,872,873,874,875,876,877,87,878,879,880,881,882,883,884,885,886,887,8,888,88,889,890,891,892,893,894,895,896,897,898,89,899,900,901,902,903,904,905,906,907,908,90,909,910,911,912,913,914,915,916,917,918,91,919,920,921,922,923,924,925,926,927,928,92,929,930,931,932,933,934,935,936,937,938,93,939,940,941,942,943,944,945,946,947,948,94,949,950,951,952,953,954,955,956,957,958,95,959,960,961,962,963,964,965,966,967,968,96,969,970,971,972,973,974,975,976,977,978,97,979,980,981,982,983,984,985,986,987,988,98,989,990,991,992,993,994,995,996,997,998,9,999,99

也就是说这些数据里面优先级别最高的是1000，在用户输入的所有数据中，和这些数据进行匹配，如果找到了这个数据，则进行输出。

#include <iostream>
    #include <cmath>
    #include<algorithm>
    using namespace std;
    
    int mydata[1002] =
    { 
        1000,100,10,101,102,103,104,105,106,107,108,109,110,1,111,11,112,113,114,115,116,117,118,119,120,121,12,122,123,124,125,126,127,128,129,130,131,13,132,133,134,135,136,137,138,139,140,141,14,142,143,144,145,146,147,148,149,150,151,15,152,153,154,155,156,157,158,159,160,161,16,162,163,164,165,166,167,168,169,170,171,17,172,173,174,175,176,177,178,179,180,181,18,182,183,184,185,186,187,188,189,190,191,19,192,193,194,195,196,197,198,199,200,201,20,202,203,204,205,206,207,208,209,210,211,21,212,213,214,215,216,217,218,219,220,221,222,2,22,223,224,225,226,227,228,229,230,231,232,23,233,234,235,236,237,238,239,240,241,242,24,243,244,245,246,247,248,249,250,251,252,25,253,254,255,256,257,258,259,260,261,262,26,263,264,265,266,267,268,269,270,271,272,27,273,274,275,276,277,278,279,280,281,282,28,283,284,285,286,287,288,289,290,291,292,29,293,294,295,296,297,298,299,300,301,302,30,303,304,305,306,307,308,309,310,311,312,31,313,314,315,316,317,318,319,320,321,322,32,323,324,325,326,327,328,329,330,331,332,333,3,33,334,335,336,337,338,339,340,341,342,343,34,344,345,346,347,348,349,350,351,352,353,35,354,355,356,357,358,359,360,361,362,363,36,364,365,366,367,368,369,370,371,372,373,37,374,375,376,377,378,379,380,381,382,383,38,384,385,386,387,388,389,390,391,392,393,39,394,395,396,397,398,399,400,401,402,403,40,404,405,406,407,408,409,410,411,412,413,41,414,415,416,417,418,419,420,421,422,423,42,424,425,426,427,428,429,430,431,432,433,43,434,435,436,437,438,439,440,441,442,443,444,4,44,445,446,447,448,449,450,451,452,453,454,45,455,456,457,458,459,460,461,462,463,464,46,465,466,467,468,469,470,471,472,473,474,47,475,476,477,478,479,480,481,482,483,484,48,485,486,487,488,489,490,491,492,493,494,49,495,496,497,498,499,500,501,502,503,504,50,505,506,507,508,509,510,511,512,513,514,51,515,516,517,518,519,520,521,522,523,524,52,525,526,527,528,529,530,531,532,533,534,53,535,536,537,538,539,540,541,542,543,544,54,545,546,547,548,549,550,551,552,553,554,555,5,55,556,557,558,559,560,561,562,563,564,565,56,566,567,568,569,570,571,572,573,574,575,57,576,577,578,579,580,581,582,583,584,585,58,586,587,588,589,590,591,592,593,594,595,59,596,597,598,599,600,601,602,603,604,605,60,606,607,608,609,610,611,612,613,614,615,61,616,617,618,619,620,621,622,623,624,625,62,626,627,628,629,630,631,632,633,634,635,63,636,637,638,639,640,641,642,643,644,645,64,646,647,648,649,650,651,652,653,654,655,65,656,657,658,659,660,661,662,663,664,665,666,6,66,667,668,669,670,671,672,673,674,675,676,67,677,678,679,680,681,682,683,684,685,686,68,687,688,689,690,691,692,693,694,695,696,69,697,698,699,700,701,702,703,704,705,706,70,707,708,709,710,711,712,713,714,715,716,71,717,718,719,720,721,722,723,724,725,726,72,727,728,729,730,731,732,733,734,735,736,73,737,738,739,740,741,742,743,744,745,746,74,747,748,749,750,751,752,753,754,755,756,75,757,758,759,760,761,762,763,764,765,766,76,767,768,769,770,771,772,773,774,775,776,777,7,77,778,779,780,781,782,783,784,785,786,787,78,788,789,790,791,792,793,794,795,796,797,79,798,799,800,801,802,803,804,805,806,807,80,808,809,810,811,812,813,814,815,816,817,81,818,819,820,821,822,823,824,825,826,827,82,828,829,830,831,832,833,834,835,836,837,83,838,839,840,841,842,843,844,845,846,847,84,848,849,850,851,852,853,854,855,856,857,85,858,859,860,861,862,863,864,865,866,867,86,868,869,870,871,872,873,874,875,876,877,87,878,879,880,881,882,883,884,885,886,887,8,888,88,889,890,891,892,893,894,895,896,897,898,89,899,900,901,902,903,904,905,906,907,908,90,909,910,911,912,913,914,915,916,917,918,91,919,920,921,922,923,924,925,926,927,928,92,929,930,931,932,933,934,935,936,937,938,93,939,940,941,942,943,944,945,946,947,948,94,949,950,951,952,953,954,955,956,957,958,95,959,960,961,962,963,964,965,966,967,968,96,969,970,971,972,973,974,975,976,977,978,97,979,980,981,982,983,984,985,986,987,988,98,989,990,991,992,993,994,995,996,997,998,9,999,99
    };
    
    int ary[500003];
    
    int main()
    { 
        int n,i;
        while(cin>>n)
        { 
            for(i=0; i<n; i++)
            { 
                cin>>ary[i];
            }
    
    
            // 注意循环外层是这一千个数
            for(int t=0; t<1000; t++)
            { 
                for(i=0; i<n; i++)
                { 
                    // 如果找到了，输出，并且修改为-1，没得重复操作
                    if(mydata[t]==ary[i])
                    { 
                        cout<<ary[i];
                        ary[i]=-1;
                    }
                }
            }
            cout<<endl;
        }
        return 0;
    }

再次提交代码，就可以发现结果正确了。

总而言之就是在这种 有界数据集运算中投机取巧，先给用户算好，然后用户使用的时候直接取就好了。虽说这个操作有些……猛？丝毫没有美感。但是有没有感觉 `简单粗暴` ？  
两次操作都是如此，简单粗暴输出一堆预期结果，然后再简单粗暴地查询。

### 关于优化 ###

简单粗暴查询时可以优化，可以考虑使用map，用户输入的时候直接写入map，键值对嘛，键就是用户输入的值，值就是用户输入的值出现的次数。输出的时候直接遍历我们已经生成的数组，取map中对应的元素，如果值是0不输出，否则循环输出。

### 总结 ###

一如既往的简单粗暴，但是丝毫没有美感，希望得到帮助，指教更好的解决方法。

> Smileyan  
> 2019年9月19日 17:32