雅礼集训 Day6 T1 Merchant 解题报告

Merchant

题目描述

有(n)个物品，第(i)个物品有两个属性(k_i,b_i)，表示它在时刻(x)的价值为(k_i imes x+b_i).

当前处于时刻(0)，你可以选择不超过(m)个物品，使得存在某个整数时刻(t,t≥ 0)，你选择的所有物品的总价值大于等于(S).

给出(S)，求(t)的最小值。

输入输出格式

输入格式

第一行三个整数(n,m,S).

接下来(n)行，第(i)行两个整数(k_i,b_i).

输出格式

一行一个整数表示答案.

数据范围

对于所有数据，有(1le mle nle 10^6,-10^9 le b_i le 10^9,-10^6 le k_i le 10^6,0 le S le 10^{18}).

数据保证有解，且答案不超过(10^9)。

( ext{Subtask}1(22\%)), (n ≤ 20).
( ext{Subtask}2(36\%)), (n ≤ 10^5),(0 ≤ k_i ≤ 10^4).
( ext{Subtask}3(8\%)), (k_i ≤ 0).
( ext{Subtask}4(12\%)), (n ≤ 10^5).
( ext{Subtask}5(22\%)), 没有特殊的约束。

一开始大家都想二分(t)

但很快发现这样是不对哒

可事实上又是可以哒

(t)的造成的最大的可取集合在值域上要么单调增，要么先单减后单增。

对于后者，我们先判(0)，然后二分就行了

发现这样如果sort是(nlognlog1e9)哒

但找第k大可以(O(n))

实现是快排只进入一边

可以用(nth\_element)

Code:

#include <cstdio>
#include <algorithm>
#define ll long long
const int N=1e6+10;
int n,m;
ll k[N],b[N],d[N],S;
ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-f;c=getchar();}
    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    return x*f;
}
bool check(ll t)
{
    for(int i=1;i<=n;i++)
        d[i]=k[i]*t+b[i];
    std::nth_element(d+1,d+n-m,d+1+n);
    ll sum=0;
    for(int i=n;i>n-m;i--)
    {
        sum+=d[i]>0?d[i]:0;
        if(sum>=S) return true;
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    S=read();
    for(int i=1;i<=n;i++)
        k[i]=read(),b[i]=read();
    ll l=0,r=1e9;
    if(check(l)) return puts("0"),0;
    while(l<r)
    {
        ll mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld
",l);
    return 0;
}

2018.10.6