| ||||||||||
| 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