題目鏈接：點擊查看

題目大意：初始時給出一個鏈表，需要按照要求排序：

當(dāng)結(jié)點中的值為負(fù)數(shù)時，需要排在最前面

當(dāng)結(jié)點中的值為非負(fù)數(shù)且小于閾值k時，排在中間

當(dāng)結(jié)點中的值大于閾值k時，排在最后

在整體排序的同時盡可能不要改變原始順序

題目分析：有了上次做模擬鏈表題的經(jīng)驗后，這個題目就順手多了，因為規(guī)則明確將排序的要求分為了三個等級，那么我們在儲存鏈表時順便儲存一下該結(jié)點的等級即可，最后從頭結(jié)點跑一邊鏈表，給每個結(jié)點編上序號，這樣在排序的時候，優(yōu)先級先按照等級來排序，若等級相同按照序號排序即可

有一個很惡心人的坑點，真的服了pat的惡心人能力了，刷波牛

測試點4，數(shù)據(jù)會給出很多單結(jié)點，也就是跟題目中所描述的鏈表沒有任何關(guān)系的結(jié)點，我們需要將其排除后再排序然后輸出，這個挺好處理的，就是鬼能想到啊，我們只需要在給鏈表中的每個結(jié)點編號的同時保留cnt，用cnt代替n即可

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Node {int date,next;int flag;int id; }node[N];int ans[N];bool cmp(int a,int b) {Node aa=node[a];Node bb=node[b];if(aa.flag!=bb.flag)return aa.flag>bb.flag;return aa.id<bb.id; }int main() { // freopen("input.txt","r",stdin);int head,n,k;scanf("%d%d%d",&head,&n,&k);for(int i=1;i<=n;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);node[a].date=b;node[a].next=c;if(node[a].date<0)node[a].flag=2;else if(node[a].date<=k)node[a].flag=1;elsenode[a].flag=0;}int cnt=0;for(int i=head;i!=-1;i=node[i].next){ans[++cnt]=i;node[i].id=cnt;}sort(ans+1,ans+1+cnt,cmp);for(int i=1;i<=cnt;i++){if(i!=cnt)printf("%05d %d %05d\n",ans[i],node[ans[i]].date,ans[i+1]);elseprintf("%05d %d %d\n",ans[i],node[ans[i]].date,-1);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的PAT (Basic Level) 1075 链表元素分类(模拟)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。