Luogu

BZOJ

分析

猜想一波:最长的天数-购买外卖的总次数的函数图像是单峰的。

于是可以三分这个总次数。

考虑如何求出这个最长的天数。首先把所有外卖按价格排序,因为显然我们会购买尽量多的便宜的没有过期的外卖。

假设对于最便宜的外卖,过期的天数是 $s$ ,那么我们一定会每次买 $s$ 份。其它外卖类似。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200+10;

ll m,f,n;
struct food { ll p,s; } a[N];
bool operator <(food a,food b) { return a.p<b.p; }

inline ll calc(ll c) {
    ll cnt=m-f*c,ans=0,t=0;
    if (cnt<=0) return 0;
    for (re int i=1;i<=n;++i) {
        if (a[i].s>t) {
            ll d=a[i].s-t;
            if (1.0*a[i].p*c*d<=cnt) ans+=c*d,cnt-=a[i].p*c*d;
            else { ans+=cnt/a[i].p; break; } 
            t=a[i].s;
        }
    }
    return ans;
}

int main() {
    m=read(),f=read(),n=read();
    for (re int i=1;i<=n;++i) a[i].p=read(),a[i].s=read()+1;
    sort(a+1,a+n+1);
    ll L=0,R=m/f,ans=0;
    while (R-L>=5) {
        ll a=L+(R-L+1)/3,b=R-(R-L+1)/3;
        ll A=calc(a),B=calc(b);
        if (A<=B) L=a; else R=b;
    }
    for (re ll i=L;i<=R;++i) ans=max(ans,calc(i));
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 15 PM