首页 > 代码库 > HDU 6040 Hints of sd0061 思维
HDU 6040 Hints of sd0061 思维
题目链接: 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; }
思考: 我学到了一个小小的skill, 如果对一个数组进行排序如果还想保留下标的信息的话, 不妨再创建一个下标数组, 然后写好cmp函数, 这时候排序的仅仅是下标, 不仅达到了目的, 还保留了原数组, 很巧妙, 这是一道很费脑筋的题, 只有多练才能在正式的比赛上想到这种方法吧
HDU 6040 Hints of sd0061 思维
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。