Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

【O(n*logn)水过】注意一点两个人相碰和两个人穿过彼此有区别吗?没有对吧,内含具体分析

Posted by WilliamACM at 2013-03-18 22:56:25 on Problem 2772
两个人相碰和两个人穿过彼此没有区别。
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator