BZOJ 3874: [Ahoi2014]宅男计划

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
HINT
题解
代码

Description

【故事背景】

自从迷上了拼图，JYY就变成了个彻底的宅男。为了解决温饱问题，JYY

不得不依靠叫外卖来维持生计。

【问题描述】

外卖店一共有N种食物，分别有1到N编号。第i种食物有固定的价钱Pi和保质期Si。第i种食物会在Si天后过期。JYY是不会吃过期食物的。

比如JYY如果今天点了一份保质期为1天的食物，那么JYY必须在今天或

者明天把这个食物吃掉，否则这个食物就再也不能吃了。保质期可以为0天，这

样这份食物就必须在购买当天吃掉。

JYY现在有M块钱，每一次叫外卖需要额外付给送外卖小哥外送费F元。

送外卖的小哥身强力壮，可以瞬间给JYY带来任意多份食物。JYY想知道，在

满足每天都能吃到至少一顿没过期的外卖的情况下，他可以最多宅多少天呢？

Input

第一行包含三个整数M，F和N。

接下来N行，第i行包含两个整数Pi和Si。

Output

输出仅包含一行一个整数表示JYY可以宅的最多的天数。

Sample Input

32 5 2
5 0
10 2

Sample Output

HINT

【样例说明】

JYY的最佳策略是：

第一天买一份食物1和一份食物2并且吃一份食物1；

第二天吃一份食物2；

第三天买一份食物1并且吃掉。

【数据规模与约定】

对于100%的数据满足0<=Si<=10^18,1<=F,Pi,M<=10^18,1<=N<=200

题解

我们这么想，如果我们购买次数少了，那么就可能导致要被迫购买一些保质期比较长但是贵的东西，是不划算的；如果我们购买次数多了，那么我们花费在小哥身上的钱就过多了，那么给自己买吃的总金额会较少，也是不划算的、、所以、、我们猜想！【我还记得当时有人临场证明，然后其他题目没写完、、、但是他证出来了，作为蒟蒻的我没证出来，也没有他考的高、、】把购买次数作为自变量，生存天数作为因变量，这是一个凸函数，所以我们可以用三分法寻找极值点。【那么我悄悄的告诉你，其实枚举购买次数，可以60分、】然后我们看得到了购买次数，如何快速计算生存天数，其实是可以贪心的，我们先预处理把那些效果相同但是价格更贵的食物去掉，然后按照保质期排序贪心！然后配合刚才的三分法就能A掉了！【我擦、、我Wa了一次80因为我把三分法写成了四分法=W=果然，数学是硬伤、、、、还有一句话，数据留邮！】

代码

/*
  Author:WNJXYK
  WebSite:http://wnjxyk.cn
  Weibo:http://weibo.com/WNJXYK
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=205;
struct Food{
    long long s,p;
    Food(){}
    Food(long s0,long long p0){
        s=s0;p=p0;
    }
};
inline bool cmpFood(Food a,Food b){
    if (a.s>b.s) return true;
    if (a.s==b.s && a.p<b.p) return true;
    return false;
}
inline bool cmpFoodInMoney(Food a,Food b){
    if (a.s<b.s) return true;
    return false;
}
inline long long remax(long long a,long long b){
    if (a>b) return a;
    return b;
}
inline long long remin(long long a,long long b){
    if (a<b) return a;
    return b;
}
long long M,F;
long long minPrice;
int n;
Food food[Maxn];
inline void init(){
    int tmpN=n;
    int nowPoint=1;
    minPrice=food[1].p;
    sort(food+1,food+n+1,cmpFood);
    for (int i=2;i<=n;i++){
        minPrice=remin(minPrice,food[i].p);
        if (food[i].s<=food[nowPoint].s && food[i].p>food[nowPoint].p){
            --tmpN;
            food[i].s=-1;
        }else
            nowPoint=i;
    }
    sort(food+1,food+n+1,cmpFood);
    n=tmpN;
    sort(food+1,food+n+1,cmpFoodInMoney);
}
long long Ans;
long long left,right,lmid,rmid;
long long lmidAns,rmidAns;
inline long long calc(long long ts);
inline void solve(){
    left=1;right=M/(F+minPrice);
    Ans=remax(calc(left),calc(right));
    while(left+25<right){
        lmid=left+(right-left)/(long long)3;
        rmid=left+(right-left)*(long long)2/(long long)3;
        lmidAns=calc(lmid);
        rmidAns=calc(rmid);
        if (lmidAns>rmidAns){
            Ans=remax(Ans,lmidAns);
            right=rmid;
        }else{
            Ans=remax(Ans,rmidAns);
            left=lmid;
        }
    }
    for (long long k=left;k<=right;k++){
        Ans=remax(Ans,calc(k));
    }
    printf("%lldn",Ans);
}
inline long long calc(long long ts){
    long long m=M-(long long)F*(long long)ts;
    if (m<0) return 0;
    long long ans=0,days=0;
    for (int i=1;i<=n;i++){
        if (days<=food[i].s){
            long long ld=food[i].s-days+1;
            long long dd=remin(ld,m/(long long)food[i].p/(long long)ts);
            ans+=dd*ts;
            m-=(long long)food[i].p*(long long)ts*(long long)dd;
            days+=dd;
        }
        if (days<=food[i].s){
            long long v=remin(ts,m/(long long)food[i].p);
            ans+=v;
            m-=food[i].p*v;
            days++;
        }
    }
    return ans;
}
int main(){
    //freopen("food.in","r",stdin);
    //freopen("food.out","w",stdout);
    scanf("%lld%lld%d",&M,&F,&n);
    for (int i=1;i<=n;i++) scanf("%lld%lld",&food[i].p,&food[i].s);
    init();
    solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

Author:WNJXYK

WebSite:http://wnjxyk.cn

Weibo:http://weibo.com/WNJXYK

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int Maxn=205;

struct Food{

long long s,p;

Food(){}

Food(long s0,long long p0){

s=s0;p=p0;

}

};

inline bool cmpFood(Food a,Food b){

if (a.s>b.s) return true;

if (a.s==b.s && a.p<b.p) return true;

return false;

}

inline bool cmpFoodInMoney(Food a,Food b){

if (a.s<b.s) return true;

return false;

}

inline long long remax(long long a,long long b){

if (a>b) return a;

return b;

}

inline long long remin(long long a,long long b){

if (a<b) return a;

return b;

}

long long M,F;

long long minPrice;

int n;

Food food[Maxn];

inline void init(){

int tmpN=n;

int nowPoint=1;

minPrice=food[1].p;

sort(food+1,food+n+1,cmpFood);

for (int i=2;i<=n;i++){

minPrice=remin(minPrice,food[i].p);

if (food[i].s<=food[nowPoint].s && food[i].p>food[nowPoint].p){

--tmpN;

food[i].s=-1;

}else

nowPoint=i;

}

sort(food+1,food+n+1,cmpFood);

n=tmpN;

sort(food+1,food+n+1,cmpFoodInMoney);

}

long long Ans;

long long left,right,lmid,rmid;

long long lmidAns,rmidAns;

inline long long calc(long long ts);

inline void solve(){

left=1;right=M/(F+minPrice);

Ans=remax(calc(left),calc(right));

while(left+25<right){

lmid=left+(right-left)/(long long)3;

rmid=left+(right-left)*(long long)2/(long long)3;

lmidAns=calc(lmid);

rmidAns=calc(rmid);

if (lmidAns>rmidAns){

Ans=remax(Ans,lmidAns);

right=rmid;

}else{

Ans=remax(Ans,rmidAns);

left=lmid;

}

for (long long k=left;k<=right;k++){

Ans=remax(Ans,calc(k));

}

printf("%lldn",Ans);

}

inline long long calc(long long ts){

long long m=M-(long long)F*(long long)ts;

if (m<0) return 0;

long long ans=0,days=0;

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

if (days<=food[i].s){

long long ld=food[i].s-days+1;

long long dd=remin(ld,m/(long long)food[i].p/(long long)ts);

ans+=dd*ts;

m-=(long long)food[i].p*(long long)ts*(long long)dd;

days+=dd;

}

if (days<=food[i].s){

long long v=remin(ts,m/(long long)food[i].p);

ans+=v;

m-=food[i].p*v;

days++;

}

return ans;

}

int main(){

//freopen("food.in","r",stdin);

//freopen("food.out","w",stdout);

scanf("%lld%lld%d",&M,&F,&n);

for (int i=1;i<=n;i++) scanf("%lld%lld",&food[i].p,&food[i].s);

init();

solve();

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑