题解：P13216 [GCJ 2015 #1A] Haircut

· · 题解

题目传送门

前言

嗯？时限 5.00s \sim 10.00s？

思路

显然，这题不需要这么多的时限。我们来说 1s 内的做法。

二分思路不难想吧，N \le 10^9，显然不带根号，那肯定带 \log，不用猜了，二分。

直接上二分答案模板。二分第 N 位顾客开始理发的时间。

模板如下。

while(l<=r){
    int mid=l+r>>1;
    if(check(mid)) ans=mid,r=mid-1;
    else l=mid+1;
}

考虑 check 函数的写法。

假设第 N 位顾客开始理发的时间为 mid，看看能否在前 mid 的时间内理发理到第 N 位顾客。

check 函数如下。

bool check(int mid){
    int cnt=0;
    for(int i=1;i<=b;i++){
        cnt+=mid/m[i];
        if(mid%m[i]) cnt++;
    }return cnt>=n;
}

二分完后，假设这个时间前理发顾客数为 cnt，答案即为第 N-cnt 位空闲无事的理发师。

代码

未卡常版：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1005;
int b,n,m[N],a[N];
bool check(int mid){
    int cnt=0;
    for(int i=1;i<=b;i++){
        cnt+=mid/m[i];
        if(mid%m[i]) cnt++;
    }return cnt>=n;
}
signed main(){
    int t;scanf("%lld",&t);
    for(int q=1;q<=t;q++){
        scanf("%lld%lld",&b,&n);
        for(int i=1;i<=b;i++) scanf("%lld",m+i);
        int l=0,r=1e12,ans;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)) ans=mid,r=mid-1;
            else l=mid+1;
        }
        int cnt1=0,cnt2=0;
        for(int i=1;i<=b;i++){
            cnt2+=(ans-1)/m[i];
            if((ans-1)%m[i]) cnt2++;
            else a[++cnt1]=i;
        }
        printf("Case #%lld: %lld\n",q,a[n-cnt2]);
    }return 0;
}

也是轻松 41ms。

卡个常，卡过 35ms，轻松拿下目前最优解。

顺便夸赞一下这题的满分分数。（33 分？）

记录。

啊哈？只有 2 个测试点？