题意：给定一个单链表 ，现在jiubei和Kwords想玩一个叫做链表取数的游 戏，jiubei每次取出链表的表头，Kwords需要在剩余的结点中，从头开始找到第一个比jiubei所取的值 更大的结点，如果无法找到这样的结点，则游戏结束。 在游戏过程中，两个人每取出一个结点，便会将这个节点连接在自己的链表尾部，直至游戏结束，并且 每次取出一个结点，该结点前后的两个结点会连结，即前一个结点会指向后一个节点(无后结点则指向 NULL )。 现在你需要计算两人的游戏结果，并分别打印两人的链表结果。
题解：用线段树维护区间最小值，已经放入链表的数修改为已经访问，忽略不计，单点修改，区间查询。
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+14; const int inf=1e9; struct node { int l,r; int sum; }segTree[maxn*4]; struct lnode { int address; int data; int next; }Node[maxn],lb1[maxn]; vector<lnode> v2,v3; int visit[maxn]; int tol1=0; int in[maxn]; void build (int i,int l,int r) { segTree[i].l=l; segTree[i].r=r; segTree[i].sum=inf; if (l==r) { segTree[i].sum=in[l]; return; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); segTree[i].sum=min(segTree[i<<1].sum,segTree[i<<1|1].sum); } void update (int i,int t) { if (segTree[i].l==segTree[i].r) { segTree[i].sum=inf; return; } int mid=(segTree[i].l+segTree[i].r)>>1; if (t<=mid) update(i<<1,t); else update(i<<1|1,t); segTree[i].sum=min(segTree[i<<1].sum,segTree[i<<1|1].sum); } int query (int i,int l,int r) { if (l==segTree[i].l&&r==segTree[i].r) return segTree[i].sum; int mid=(segTree[i].l+segTree[i].r)>>1; int ans=inf; if (r<=mid) return min(ans,query(i<<1,l,r)); else if (l>mid) return min(ans,query(i<<1|1,l,r)); else return min(ans,min(query(i<<1,l,mid),query(i<<1|1,mid+1,r))); } int main () { int head,N; scanf("%d%d",&head,&N); for (int i=0;i<N;i++) { int address,data,next; scanf("%d%d%d",&address,&data,&next); Node[address].address=address; Node[address].data=data; Node[address].next=next; } while (head!=-1) { lb1[++tol1]=Node[head]; in[Node[head].data]=tol1; head=Node[head].next; } build(1,1,tol1); for (int i=1;i<=tol1;i++) { if (visit[i]==1) continue; v2.push_back(lb1[i]); update(1,lb1[i].data); visit[i]=1; int ans=query(1,lb1[i].data,tol1); if (ans==inf) break; v3.push_back(lb1[ans]); update(1,lb1[ans].data); visit[ans]=1; } if (v2.size()==0) printf("-1\n"); else { printf("%05d %d ",v2[0].address,v2[0].data); for (int i=1;i<v2.size();i++) { printf("%05d\n%05d %d ",v2[i].address,v2[i].address,v2[i].data); } printf("-1\n"); } if (v3.size()==0) printf("-1\n"); else { printf("%05d %d ",v3[0].address,v3[0].data); for (int i=1;i<v3.size();i++) { printf("%05d\n%05d %d ",v3[i].address,v3[i].address,v3[i].data); } printf("-1\n"); } return 0; }
原文链接: https://www.cnblogs.com/zhanglichen/p/12460849.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/372635
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
