题目链接：点击打开链接
题目大意：同 PAT-B-1015 德才论。
解题思路：这题卡数据比较厉害，同一个代码 乙级 AC了，但是 甲级 有2个数据点 TLE，发现看乙级代码是因为一开始就划分好四个数组，导致排序需要四次，按理说应该问题不大，因为的是嵌套的for，但是题目数据比较强，卡点了，所以用自定义优先级来排序即可，这样就可以宏观上划分为一组。
TLE 代码（乙级AC，甲级TLE）
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1e5+10; struct node { string id; int d,c,dc; }nds1[maxn], nds2[maxn], nds3[maxn], nds4[maxn]; int cmp(node n1,node n2) { if(n1.dc==n2.dc && n1.d==n2.d) return n1.id<n2.id; else if(n1.dc==n2.dc) return n1.d>n2.d; return n1.dc>n2.dc; } int main() { int n,L,H,d,c,l1,l2,l3,l4; char id[10]; while(~scanf("%d%d%d",&n,&L,&H)) { l1=l2=l3=l4=0; for(int i=0;i<n;i++) { scanf("%s%d%d",id,&d,&c); if(d>=H && c>=H) nds1[l1].id=id, nds1[l1].d=d, nds1[l1].c=c, nds1[l1++].dc=d+c; else if(d>=H && c<H && c>=L) nds2[l2].id=id, nds2[l2].d=d, nds2[l2].c=c, nds2[l2++].dc=d+c; else if(d<H && c<H && d>=c && c>=L && d>=L) nds3[l3].id=id, nds3[l3].d=d, nds3[l3].c=c, nds3[l3++].dc=d+c; else if(d>=L && c>=L) nds4[l4].id=id, nds4[l4].d=d, nds4[l4].c=c, nds4[l4++].dc=d+c; } sort(nds1,nds1+l1,cmp); sort(nds2,nds2+l2,cmp); sort(nds3,nds3+l3,cmp); sort(nds4,nds4+l4,cmp); printf("%d\n",l1+l2+l3+l4); for(int i=0;i<l1;i++) printf("%s %d %d\n",nds1[i].id.c_str(),nds1[i].d,nds1[i].c); for(int i=0;i<l2;i++) printf("%s %d %d\n",nds2[i].id.c_str(),nds2[i].d,nds2[i].c); for(int i=0;i<l3;i++) printf("%s %d %d\n",nds3[i].id.c_str(),nds3[i].d,nds3[i].c); for(int i=0;i<l4;i++) printf("%s %d %d\n",nds4[i].id.c_str(),nds4[i].d,nds4[i].c); } return 0; }
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1e5+10; struct node { string id; int d,c,dc; int pri; }nds[maxn]; int cmp(node n1,node n2) { if(n1.pri==n2.pri) { if(n1.dc==n2.dc && n1.d==n2.d) return n1.id<n2.id; else if(n1.dc==n2.dc) return n1.d>n2.d; return n1.dc>n2.dc; } return n1.pri<n2.pri; } int main() { int n,L,H,d,c,l; char id[10]; while(~scanf("%d%d%d",&n,&L,&H)) { l=0; for(int i=0;i<n;i++) { scanf("%s%d%d",id,&d,&c); if(d>=L && c>=L) { nds[l].id=id, nds[l].d=d, nds[l].c=c, nds[l].dc=d+c; if(d>=H && c>=H) nds[l].pri=1; else if(d>=H && c<H && c>=L) nds[l].pri=2; else if(d<H && c<H && d>=c && c>=L && d>=L) nds[l].pri=3; else if(d>=L && c>=L) nds[l].pri=4; l++; } } sort(nds,nds+l,cmp); printf("%d\n",l); for(int i=0;i<l;i++) printf("%s %d %d\n",nds[i].id.c_str(),nds[i].d,nds[i].c); } return 0; }
