首页 > 代码库 > CF830B:Cards Sorting
CF830B:Cards Sorting
对叠放着的n张牌,第i张牌写有数字Ai,进行操作:将牌堆顶的牌取出,若是当前牌堆最小值就扔掉,否则放到牌堆底,求牌堆空时操作次数。
怎么看怎么像约瑟夫。。不过约瑟夫DP我不太熟,于是就yy了一下
“当前最小值”??优先队列。把Ai和i绑起来扔到优先队列里,就可以知道下一步要跳到哪里。
有个问题:如果有多个Ai怎么办???把这些相同的数字列出来,下标升序排列,假如上一次抽完牌的位置是now,那么它在把所有这些相同的数字取完后,会走到“离now最近的第一个比now小的下标”那里
因此优先队列中以数字大小为第一关键字而位置为第二,每次取出相同数字的所有位置,利用单调性边取边直接判断我们要找的“离now最近的第一个比now小的下标”(然而代码中我傻了,拿下标出来二分查找)
这样统计答案还有个小问题:有些牌已经被抽掉了,所以用下标统计答案是不行滴!那就加个树状数组吧,复杂度O(nlog2n)
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<cstring> 6 #include<queue> 7 //#include<iostream> 8 using namespace std; 9 10 struct heapnode 11 { 12 int v,id; 13 bool operator < (const heapnode &b) const 14 {return v<b.v || (v==b.v && id<b.id);} 15 bool operator > (const heapnode &b) const {return b<*this;} 16 }; 17 priority_queue<heapnode,vector<heapnode>,greater<heapnode> > q; 18 int n; 19 int x; 20 #define maxn 100011 21 int list[maxn],len; 22 #define LL long long 23 int find(int x) 24 { 25 if (x<=list[1]) return 0; 26 int L=1,R=len; 27 while (L<R) 28 { 29 int mid=(L+R+1)>>1; 30 if (list[mid]>=x) R=mid-1; 31 else L=mid; 32 } 33 return L; 34 } 35 struct BIT 36 { 37 int a[maxn]; 38 int lowbit(int x) {return x&-x;} 39 int query(int x) 40 { 41 x++; 42 int ans=0; 43 for (;x;x-=lowbit(x)) ans+=a[x]; 44 return ans; 45 } 46 void add(int x,int v) 47 { 48 x++; 49 for (;x<=n;x+=lowbit(x)) a[x]+=v; 50 } 51 }t; 52 int main() 53 { 54 scanf("%d",&n); 55 for (int i=0;i<n;i++) 56 { 57 scanf("%d",&x); 58 q.push((heapnode){x,i}); 59 t.add(i,1); 60 } 61 int now=0;LL ans=1; 62 while (!q.empty()) 63 { 64 int p=q.top().v; 65 list[len=1]=q.top().id; 66 q.pop(); 67 while (!q.empty() && q.top().v==p) 68 { 69 list[++len]=q.top().id; 70 q.pop(); 71 } 72 int tmp=find(now); 73 if (!tmp) 74 { 75 ans=ans+t.query(list[len])-t.query(now); 76 now=list[len]; 77 } 78 else 79 { 80 ans=ans+t.query(list[tmp])+t.query(n-1)-t.query(now); 81 now=list[tmp]; 82 } 83 for (int i=1;i<=len;i++) t.add(list[i],-1); 84 } 85 printf("%I64d\n",ans); 86 return 0; 87 }
CF830B:Cards Sorting
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。