這幾天做了幾道隨機(jī)生成數(shù)組的題，且需要用nth-elemeng函數(shù)，并且都是北航出的多校題……

首先我們先貼一下隨機(jī)生成數(shù)組函數(shù)的代碼：

1 unsigned x = A, y = B, z = C; 2 unsigned rng61() { 3 unsigned t; 4 x ^= x << 16; 5 x ^= x >> 5; 6 x ^= x << 1; 7 t = x; 8 x = y; 9 y = z; 10 z = t ^ x ^ y; 11 return z; 12 } View Code

這個(gè)函數(shù)的原理原諒我不太懂，就不多說(shuō)了-_-||。

接下來(lái)來(lái)談一下stl中的一個(gè)nth_element函數(shù)，這個(gè)函數(shù)對(duì)于一個(gè)數(shù)組、容器（我們就用最普通的數(shù)組a來(lái)進(jìn)行討論），假設(shè)我們需要求這個(gè)數(shù)組中的第k個(gè)元素，那么我們只需nth_element(a,a+k,a+n)（下標(biāo)從0開始），那么a中第k小的數(shù)將會(huì)出現(xiàn)在第k個(gè)位置，且能夠保證前k-1個(gè)元素都比它小，后面的元素都比它大（但是這兩堆數(shù)是無(wú)序的），復(fù)雜度為O(n)，該函數(shù)的一般用法為：nth_element(開始位置，所求位置，結(jié)束位置）。stl是個(gè)神奇的東西，里面還有max_element,min_element函數(shù)，具體用法請(qǐng)點(diǎn)擊鏈接：http://www.cnblogs.com/Dillonh/p/9042456.html。

順便貼一下這幾天做的兩道題：

第一道為昨天牛客多校的J題Heritage of skywalkert，題目鏈接：https://www.nowcoder.com/acm/contest/144/J

題目：

題意：用隨機(jī)生成數(shù)組函數(shù)生成n個(gè)數(shù)，求這n個(gè)數(shù)中兩兩的lcm（最小公倍數(shù)）的最大值，n的范圍為2e6.

思路：雖說(shuō)要n個(gè)，但是我們只需要取出100個(gè)最大的即可，因?yàn)閾?jù)證明兩個(gè)數(shù)互質(zhì)的概率為（具體證明請(qǐng)自行百度），所以我們只需將這100個(gè)數(shù)求次lcm即可。

代碼實(shí)現(xiàn)如下：

1 #include <set> 2 #include <map> 3 #include <queue> 4 #include <stack> 5 #include <cmath> 6 #include <bitset> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 16 typedef long long ll; 17 typedef pair<ll, ll> pll; 18 typedef pair<ll, int> pli; 19 typedef pair<int, ll> pil;; 20 typedef pair<int, int> pii; 21 typedef unsigned long long ull; 22 23 #define lson i<<1 24 #define rson i<<1|1 25 #define bug printf("*********\n"); 26 #define FIN freopen("D://code//in.txt", "r", stdin); 27 #define debug(x) cout<<"["<<x<<"]" <<endl; 28 #define IO ios::sync_with_stdio(false),cin.tie(0); 29 30 const double eps = 1e-8; 31 const int mod = 10007; 32 const int maxn = 1e7 + 7; 33 const double pi = acos(-1); 34 const int inf = 0x3f3f3f3f; 35 const ll INF = 0x3f3f3f3f3f3f3f; 36 37 int tt, n; 38 unsigned int x, y, z; 39 ull num[maxn]; 40 41 unsigned int tang() { 42 unsigned t; 43 x ^= x << 16; 44 x ^= x >> 5; 45 x ^= x << 1; 46 t = x; 47 x = y; 48 y = z; 49 z = t ^ x ^ y; 50 return z; 51 } 52 53 ull gcd(ull a, ull b) { 54 return b == 0 ? a : gcd(b, a % b); 55 } 56 57 int main() { 58 //FIN; 59 scanf("%d", &tt); 60 int icase = 0; 61 while(tt--) { 62 scanf("%d%u%u%u", &n, &x, &y, &z); 63 for(int i = 0; i < n; i++) { 64 num[i] = tang(); 65 } 66 ull mx = 0; 67 if(n > 101) { 68 int tmp = n - 100; 69 nth_element(num, num + tmp, num + n); 70 for(int i = tmp; i < n; i++) { 71 for(int j = tmp; j < n; j++) { 72 ull tt = num[i] / gcd(num[i], num[j]) * num[j]; 73 mx = mx > tt ? mx : tt; 74 } 75 } 76 } else { 77 for(int i = 0; i < n; i++) { 78 for(int j = 0; j < n; j++) { 79 ull tt = num[i] / gcd(num[i], num[j]) * num[j]; 80 mx = mx > tt ? mx : tt; 81 } 82 } 83 } 84 printf("Case #%d: %llu\n", ++icase, mx); 85 } 86 return 0; 87 } View Code

?

第二題是2017年杭電多校的題目，Hints of sd0061（HDU6040：

題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=6040

題目：

題意：用隨機(jī)生成數(shù)組函數(shù)生成n個(gè)數(shù)，且求出第bi+1位的數(shù)，n的范圍為1e7。

思路：這題照樣需要借助nth_element函數(shù)，但是由于n太大，再加上要求m個(gè)數(shù)，復(fù)雜度妥妥地T，所以我們要想點(diǎn)優(yōu)化，我們知道nth_element的復(fù)雜度是與所求范圍來(lái)決定的，且nth_element函數(shù)會(huì)將大于某個(gè)數(shù)小于某個(gè)數(shù)分開，那么我們可以借助先求出排在后面的數(shù)，再求排在前面的數(shù)，逐步將范圍縮小，從而縮小范圍。

代碼實(shí)現(xiàn)如下：

1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int maxn = 1e7 + 7; 6 7 int n, m; 8 pair<int, int> b[105]; 9 unsigned a[maxn], num[maxn]; 10 unsigned x, y, z; 11 12 unsigned rng61() { 13 unsigned t; 14 x ^= x << 16; 15 x ^= x >> 5; 16 x ^= x << 1; 17 t = x; 18 x = y; 19 y = z; 20 z = t ^ x ^ y; 21 return z; 22 } 23 24 int main() { 25 int icase = 0; 26 while(~scanf("%d", &n)) { 27 scanf("%d%u%u%u", &m, &x, &y, &z); 28 for(int i = 0; i < m; i++) { 29 scanf("%d", &b[i].first); 30 b[i].second = i; 31 } 32 sort(b, b + m); 33 b[m].first = n; 34 for(int i = 0; i < n; i++) { 35 a[i] = rng61(); 36 } 37 printf("Case #%d:", ++icase); 38 for(int i = m - 1; i >= 0; i--) { 39 nth_element(a, a + b[i].first, a + b[i+1].first); 40 num[b[i].second] = a[b[i].first]; 41 } 42 for(int i = 0; i < m; i++) { 43 printf(" %u", num[i]); 44 } 45 printf("\n"); 46 } 47 return 0; 48 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Dillonh/p/9426329.html

總結(jié)

以上是生活随笔為你收集整理的随机生成数组函数+nth-element函数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。