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

思路

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

一眼看认为是道贪心，后来怎么想怎么不对劲，知道看到

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

个人发的最短时间）

CPP

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

二分代码如下：

CPP

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

完整代码：

CPP

#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;
}

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

文章操作

思路

代码实现

相关推荐

评论

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