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

Luojt95 · 2025-08-12 17:36:32 · 题解

题目传送门。

思路

带着神秘时间限制的好奇心来到了此题。

一眼看认为是道贪心，后来怎么想怎么不对劲，知道看到 N \le 10^9 才恍然大悟： O(TN) 以上过不去呀，只能使用 O(TB\log N) 的算法：二分！

二分找什么呢？找出理 N 个人发的最短时间，设其为 ans 分钟。而为你理发的理发师编号是多少关键就在于第 ans-1 分钟理完了多少顾客，设其为 cnt 名，然后，第 cnt+1 \sim N 名顾客对号入座，而你是最后选择的那个人，第 cnt+1 \sim N 名顾客中一共有 N-cnt 名顾客，你就自然对应了第 N-cnt 名理发师。

代码实现

check 函数如下：（ check(x) 表示理 x 个人发的最短时间）

int check(int x)
{
    int res=0;
    for(int i=1;i<=n;i++) res+=x/a[i]+1;//+1 表示理发时间从 0 开始
    return res;
}

二分代码如下：

int l=0,r=1e18,ans=-1;// 其实 r 不需要开那么大，纯属个人习惯
while(l<=r)
{
    int mid=l+r>>1;
    if(check(mid)>=k)
    {
        r=mid-1;
        ans=mid;
    }
    else
    {
        l=mid+1;
    }
}

完整代码：

#include<bits/stdc++.h>
#define int long long // 一定要开 long long ！
using namespace std;
int t,n,k;
int a[1010];
vector<int> e;
int check(int x)
{
    int res=0;
    for(int i=1;i<=n;i++) res+=x/a[i]+1;
    return res;
}
signed main()
{
    cin>>t;
    for(int Case=1;Case<=t;Case++)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        int l=0,r=1e18,ans=-1;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(check(mid)>=k)
            {
                r=mid-1;
                ans=mid;
            }
            else
            {
                l=mid+1;
            }
        }
        int pos=k-check(ans-1)-1; //记得 -1 ，时间从 0 开始
        e.clear();
        for(int i=1;i<=n;i++)
            if(!(ans%a[i])) //表示恰巧在 ans-1 时刻理完顾客发的理发师可以给你理发
                e.push_back(i);
        cout<<"Case #"<<Case<<": "<<e[pos]<<'\n';
    }
    return 0;
}