[NOIP10.6模拟赛]1.merchant题解--思维+二分

题目链接:

while(1)gugu(while(1))

闲扯

考场上怕T2正解写挂其他两题没管只打了暴力,晚上发现这题思维挺妙的

同时想吐槽出题人似乎热衷卡常...我的巨大常数现在显露无疑QAQ

分析

这道题yy出了一个似乎比solution更好理解的解法,一开始有\(n\)条一次函数,就有\(2^n\)种函数集合,显然每个集合也是一个一次函数\(T_i(x)=k_i x+b_i\)

我们把这个集合分成两种\(k_i<=0\)和\(k_i>0\),显然如果答案最后最大值的函数集合是第一种,那么显然肯定是在\(x=0\)取到的

所以我们单独把\(x=0\)拎出来考虑就可以不考虑第一种函数集合的贡献了

对于第二种\(k_i>0\)的函数集合,应该很容易发现\(max(T_i(x))\)是单调递增的的图像,可以二分找到答案要求的点

然后这题就做完了

对于0的处理其实就是把\(b_i\)最大且大于0的拿出来看看是否大于等于S就好了,虽然最后这样的函数集合不一定是第一种\(k_i<=0\)但是一定考虑进去了

二分的时候也是贪心把该点的处于前\(m\)大且大于0的单个一次函数值加起来判断一下就好了

这里有个骚操作nth_ment(l,pos,r,cmp),表示将容器中\([l,r)\)种第pos个位置的元素变成第\(pos\)大/小(视cmp函数决定)，同时pos前都是大/小于第pos大/小的元素,pos后类似

代码

#include <cstdio>

#include <cstdlib>

#include <cctype>

#include <algorithm>

#include <cctype>

#include <iostream>

#include <queue>

#include <vector>

#define ll long long

#define ri register int

using std::min;

using std::max;

using std::nth_element;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

template <class T>inline void read(T &x){

    x=0;int ne=0;char c;

    while(!isdigit(c=nc()))ne=c=='-';

    x=c-48;

    while(isdigit(c=nc()))x=(x<<3)+(x<<1)+c-48;

    x=ne?-x:x;return ;

}

const int maxn=1000005;

const int inf=0x7fffffff;

ll v[maxn],ki[maxn],bi[maxn];

int n,m;ll s;

bool ok(int x){

    for(ri i=1;i<=n;i++)v[i]=ki[i]*x+bi[i];

    nth_element(v+1,v+m,v+n+1,std::greater<ll>());

    ll sum=0;

    if(sum>=s)return 1;

    for(ri i=1;i<=m;i++){

        if(v[i]>0)sum+=v[i];

        if(sum>=s)return 1;

    }

    return 0;

}

int main(){

	freopen("merchant.in","r",stdin);

	freopen("merchant.out","w",stdout);

    read(n),read(m),read(s);

    for(ri i=1;i<=n;i++){

        read(ki[i]),read(bi[i]);

    }

    if(ok(0)){puts("0");exit(0);}

    int L=1,R=1e9,ans;

    while(L<=R){

        int mid=(L+R)>>1;

        if(ok(mid))ans=mid-1,R=mid-1;

        else L=mid+1;

    }

    printf("%d\n",ans+1);

    return 0;

}

巴特西

[NOIP10.6模拟赛]1.merchant题解--思维+二分

题目链接:

闲扯

分析

代码

最新文章

热门文章