Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
【O(n*logn)水过】注意一点两个人相碰和两个人穿过彼此有区别吗?没有对吧,内含具体分析两个人相碰和两个人穿过彼此没有区别。 H最高层 fi是每个人所在的楼层 也就是说 手里有box的人 H-fi 时间后到达H层 没有box的人 在H+fi时间后到达H层 当2*H时间过后,所有人的位置都不变,但已经有n个box被放到H层了。 所以B(要把人手里的box先加进去), ans= B/n*2*H, 如果 B%n==0 ans要减去最后那个放完box的人走的距离,如果B%n>0,要加上第B%n个先放box ,所用的时间。 P.S.好像要用longlong,没具体算,为了保险, 具体看代码: #include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N=1009; int a[N],n,H,B; #define ll long long int main() { // freopen("in.txt","r",stdin); int w;cin>>w; while(w--) { scanf("%d%d%d",&n,&H,&B); for(int i=0,f,h;i<n;i++) { scanf("%d%d",&f,&h); if(h) { B++; a[i]=H-f; }else a[i]=f+H; } ll ans=0; ans=B/n*H*2; B%=n; sort(a,a+n); if(B) ans+=a[B-1]; else ans-=2*H-a[n-1]; printf("%lld\n",ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator