2017 Multi-University Training Contest

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6040

题意：不知道北航的同学为何解释题意之前都要想一段故事，导致刚开始题意不是很懂，题意就是给你n，m，A，B，C三个点，可以用以下这段代码生成n个随机数，赋值num[N],然后给你m个数，作为m次询问赋值给q[N]。然后问你第i次询问对于区间(0,n)这个区间中第q[i]+1小的数。

unsigned x = A, y = B, z = C;

unsigned rng61() {

  unsigned t;

  x ^= x << ;

  x ^= x >> ;

  x ^= x << ;

  t = x;

  x = y;

  y = z;

  z = t ^ x ^ y;

  return z;

}

思路：好吧……我是看了别人的代码，学习了这个线性求k大的姿势，就是用了一个STL的库函数nth_element(start,start+n,end);这个函数找的是[start,end)这个左闭右开区间内部第n+1大的数，感觉这个题就是为这个函数设计的。因为他是把拍完序以后应该在下标为n的位置的数归位，n左边的数比他小，右边的数比他大（不完全快排），这个题还有一个优化的地方，就是减少排序区间。我们先处理大的询问再处理小的询问。我举个例子，比如54321，现在我要求第5小的数，是5，处理完以后数组可能是43215，5是归位的但是其他数还是乱序的。然后我再在[0,4)这个区间内部去找第4小的数，和我原来要在[0,5)这个区间内部去找第四小的数结果是一样的。这样做的优点在于我们逐渐减少了，处理的区间加快了速度。这个题是个暴力题，如果没有这个优化是会超时的。

代码：

 //Author: xiaowuga

 #include <iostream>

 #include <algorithm>

 #include <set>

 #include <vector>

 #include <queue>

 #include <cmath>

 #include <cstring>

 #include <cstdio>

 #include <ctime>

 #include <map>

 #include <bitset>

 #include <cctype>

 #define maxx INT_MAX

 #define minn INT_MIN

 #define inf 0x3f3f3f3f

 #define mem(s,ch) memset(s,ch,sizeof(s))

 #define da cout<<da<<endl

 #define uoutput(a,i,l,r) for(int i=l;i<r;i++) if(i==l) cout<<a[i];else cout<<" "<<a[i];cout<<endl;

 #define doutput(a,i,l,r) for(int i=r-1;i>=0;i--) if(i==r-1) cout<<a[i];else cout<<" "<<a[i];cout<<endl;

 const long long N=1e7+;

 using namespace std;

 typedef long long LL;

 unsigned x,y,z;

 unsigned rng61() {

   unsigned t;

   x ^= x << ;

   x ^= x >> ;

   x ^= x << ;

   t = x;

   x = y;

   y = z;

   z = t ^ x ^ y;

   return z;

 }

 unsigned num[N];

 unsigned ans[N],ca=;

 pair<int,int>q[+];

 int cmp(pair<int,int>a,pair<int,int>b){

     return a.first<b.first;

 }

 int main() {

     ios::sync_with_stdio(false);cin.tie();

     unsigned n,m;

     while(cin>>n>>m>>x>>y>>z){

         for(int i=;i<n;i++) num[i]=rng61();

         for(int i=;i<m;i++) {cin>>q[i].first;q[i].second=i;}

         sort(q,q+m,cmp);//从小到大排序

         q[m].first=n;

         q[m].second=m;

         for(int i=m-;i>=;i--){

             //我们知道q[i+1].f是大于q[i].f的所以我们根据这个性质

             //我们每次在[0,q[i+1].f)这个区间里面去找第q[i].f+1大的的数

             //我们还需要知道nth_element这个函数是把第n+1大的数放在n的下标里面

             nth_element(num,num+q[i].first,num+q[i+].first);

             ans[q[i].second]=num[q[i].first];

         }

         cout<<"Case #"<<++ca<<":";

         for(int i=;i<m;i++) cout<<" "<<ans[i];

         cout<<endl;

     }

     return ;

 }

巴特西

2017 Multi-University Training Contest - Team 1—HDU6040

最新文章

热门文章