Throw nails hdu多校联赛10 1004 水题
/*速度之差最小为1，而第一步的距离最大为500，所以501s以后速度大的距离必然大。而不是500s。这个地方wa到吐血。所以前501s暴力，后面的直接对速度和标号排序输出即可。*/#include <stdio.h>#include <cstring>#include <iostream>#include <algorithm>using namespace std;struct st{ int id,v,dis;}s[50001],temp;int ans[50001];bool cmp(struct st a,struct st b){ if(a.dis!=b.dis) return a.dis>b.dis; return a.id<b.id;}int main(){ int t,n; scanf("%d",&t); int ca=1; while(t--) { scanf("%d",&n); memset(ans,0,sizeof(ans)); memset(s,0,sizeof(s)); for(int i=1; i<=n; i++) { scanf("%d%d",&s[i].dis,&s[i].v); s[i].id=i; } int q=min(501,n); int h=0; int mm; for(int i=1; i<=q; i++) { mm=i; for(int j=i+1; j<=n; j++) { if(s[j].dis>=s[mm].dis) { if(s[j].dis==s[mm].dis) { if(s[j].id<s[mm].id) mm=j; } else mm=j; } } temp=s[i]; s[i]=s[mm]; s[mm]=temp; ans[h++]=s[i].id; for(int j=i+1;j<=n;j++) s[j].dis+=s[j].v; } printf("Case #%d:\n",ca++); if(n>501) { sort(s+502,s+n+1,cmp); for(int i=502; i<=n; i++) ans[h++]=s[i].id; } for(int i=0; i<h-1; i++) printf("%d ",ans[i]); printf("%d\n",ans[h-1]); } return 0;}