HDU 6040 Hints of sd0061 思维-蒲公英云

HDU 6040 Hints of sd0061 思维

叁歲伎倆 2022-01-05 02:28 227阅读 0赞

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

　　题目大意：给定数组a， b。要求输出和B长度相同的数组C， C[i]为在A中排名为B[i]的数，重新排A数组，使得a[i]必须是a数组中第b[i]+1大的数

　　解题思路：首先我们要把数组A求出来。第一想法就是最单纯的将A排个序，然后输出A[B[i]]，自己还恬不知耻的去交了一发，要是这都不会T，还叫啥ACM啊……

　　　　　　　好吧，我题意理解错了……自己太浮躁了，检讨一下自己。有时候数据会给的非常极端来误导你…….记住了 …. 以后不要这样了。先将B数组排序，这里用到了一个快排的思想，库函数为nth_element(a, a+k, a+n)，将第K大的元素放在数组的下标K上，左面全比他小，右面全比他大，也就是说如果k是由大到小的话可以省去一半左右的时间，这题也是卡这个的，还有一个问题就是可能会出现n < m 的情况，这时候为了加快速度可以通过b[pos[i]] == b[pos[i+1]]来提前判定。

　　代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<string>
using namespace std;
typedef long long ll;
unsigned int a[10000010];
unsigned int x,y,z;
unsigned int rng61()
{
    unsigned int t;
    x ^= x << 16;
    x ^= x >> 5;
    x ^= x << 1;
    t = x;
    x = y;
    y = z;
    z = t ^ x ^ y;
    return z;
}
int b[105];
int n,m,pos[105];
unsigned int ans[105];
bool cmp(int x,int y)
{
    return b[x]<b[y];
}
int main()
{
    int v=1;
    while(scanf("%d%d%u%u%u",&n,&m,&x,&y,&z)!=EOF)
    {
        for(int i=0;i<m;i++)
        {
            scanf("%d",&b[i]);
            pos[i]=i;
        }
        sort(pos,pos+m,cmp);//通过b的大小对下标排序。
        for(int i=0;i<n;i++)
        {
            a[i]=rng61();
        }
        b[pos[m]=m]=n;
        for(int i=m-1;i>=0;i--)
        {
            if(b[pos[i]]==b[pos[i+1]])
            {
                ans[pos[i]]=ans[pos[i+1]];
                continue;
            }
            nth_element(a,a+b[pos[i]],a+b[pos[i+1]]);
            ans[pos[i]]=a[b[pos[i]]];
        }
        printf("Case #%d:",v++);
        for(int i=0;i<m;i++)
        {
            printf(" %u",ans[i]);
        }
        printf("\n");
    }
    return 0;
}