HDU 6040 Hints of sd0061 思维

叁歲伎倆 2022-01-05 02:28 147阅读 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\]\]来提前判定。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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;
    }

思考： 我学到了一个小小的skill， 如果对一个数组进行排序如果还想保留下标的信息的话， 不妨再创建一个下标数组， 然后写好cmp函数， 这时候排序的仅仅是下标， 不仅达到了目的， 还保留了原数组， 很巧妙， 这是一道很费脑筋的题， 只有多练才能在正式的比赛上想到这种方法吧

转载于:https://www.cnblogs.com/FriskyPuppy/p/7255799.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211230/b8afef81f8b54d4f9bdba2275bf34b23.png