??? food評測傳送門

【題目描述】

　　叫外賣是一個技術活,宅男宅女們一直面對著一個很大的矛盾,如何以有限的金錢在宿舍宅得盡量久。
? 　? 外賣店一共有 N 種食物,每種食物有固定的價錢 Pi 與保質期 Si ,保質期的意義是食物會在被買的第 Si 天后過期。譬如你在今天叫了一個 Si =1 的食物,則你必須在今天或者明天吃掉它。
　??? 現在你有 M 元錢,每次叫外賣需要 F 元的運費,送外賣的小哥身強體壯,叫一次可以幫你帶來任意份任意種食物,請問在保證每天都吃到至少一份未過期食物的前提下,你最多能宅多久?
【輸入文件】
　　第一行 T 表示數據組數
　　對于每組數據,第一行三個整數 M F N
　　接下來 N 行每行兩個整數 P i S i
【輸出文件】
　　對于每組數據,在一行中輸出一個數表示最多宅的天數
【樣例輸入】
　　food.in
　　332 5 2
　　5 0
　　10 2
　　10 10 1
　　10 10
　　10 1 1
　　1 5
【樣例輸出】
　　food.out
　　3
　　0
　　8
【數據約定】
?　　30%:0 <= Si <= 10,1 <= M <= 20,1 <= N <= 10
　　100%:0 ≤ S i ≤ 2000000,1 ≤ M ≤ 2000000
　　100%:T ≤ 10,1 ≤ F ≤ M,1 ≤ N ≤ 200,1 ≤ P i ≤ M

思路：

　　覺得這題好難呀 也不知道怎么想到正解 就直接講講正解吧

?

　　solution說 ：“這是道構造貪心的好題”

　??? 發現這題無從下手，但是如果知道點外賣點了多少次就好做了（我并沒有覺得很好做???）

　　所以我們枚舉點外賣的次數 這樣我們就知道總的運費了 也就知道了買食物的總錢數

　　然后我們需要考慮的是兩次點外賣之間的間隔 這里是一個貪心

?

　　首先我們初始化的時候就要去掉那些又貴保質期又短的食物 保證食物的保質期與價格正相關

　　先說結論吧 當點外賣的兩兩之間的間隔時間相等時 可以維持天數是最多的

　　假如我們要維持6天 點2次外賣 那么在第一天和第四天點外賣花的錢是最少的

　　因為這樣子的話點的外賣中保質期最長的只需要2天就可以了 而價錢與保質期正相關

　　保質期短 價錢就少???

　　

　　我們二分每輪點外賣維持的天數

　　可以預處理出點一次外賣維持一定天數的最小價錢

　　所以這里就比較好判斷了

　　但是要注意的是 可能點一定次數的外賣并且維持一定的天數后? 還有錢剩余

　　這時就可以在最后一次點外賣的時候多點一些 維持更多的天數

CODE：

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define go(i,a,b) for(register int i=a;i<=b;i++) 5 #define yes(i,a,b) for(register int i=a;i>=b;i--) 6 #define ll long long 7 #define M 200+10 8 #define N 1000000+10 9 #define inf 21000000 10 using namespace std; 11 ll read() 12 { 13 int x=0,y=1;char c=getchar(); 14 while(c<'0'||c>'9') {if(c=='-') y=-1;c=getchar();} 15 while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();} 16 return x*y; 17 } 18 ll T,n,m,f,maxn,ans,p[M],s[M],minn[N],sm[N]; 19 void work(ll st,ll my) //step money 20 { 21 ll l=0,r=maxn; 22 while(l<r) 23 { 24 ll mid=(l+r+1)>>1; 25 if(sm[mid]*st<=my) l=mid; 26 else r=mid-1; 27 } 28 ans=max(ans,l*st+(my-sm[l]*st)/minn[l+1]); 29 } 30 int main() 31 { 32 T=read(); 33 while(T--) 34 { 35 m=read();f=read();n=read(); 36 memset(minn,77,sizeof(minn)); 37 maxn=0;ans=0; 38 go(i,1,n) 39 { 40 p[i]=read();s[i]=read()+1; 41 minn[s[i]]=min(minn[s[i]],p[i]); 42 maxn=max(maxn,s[i]); 43 } 44 yes(i,maxn-1,1) minn[i]=min(minn[i],minn[i+1]); 45 go(i,1,maxn) sm[i]=sm[i-1]+minn[i]; 46 if(!f) {printf("%lld\n",m/minn[1]);continue ;} 47 go(i,1,m/f) work(i,m-i*f); 48 printf("%lld\n",ans); 49 } 50 } View Code

?????

宅男計劃傳送門

　　和上面那題唯一不同的地方就是 數據范圍

　　這里的數據范圍是：0<=Si<=10^18,1<=F,Pi,M<=10^18,1<=N<=200

　　于是用上面的代碼就會超時啦

　　然后發現點外賣的次數是可以三分的（當然不是我發現的）

?????? 以下摘自 gql's blog :

　　　　可以證明,外賣的輪次與存活天數是個二次函數關系

　　　　來下面我再來證明下Qw

　　　　首先感性理解下,假如我現在有很多錢,我只讓快遞小哥來一次,我最多只能活保質期max天嘛

　　　　然后如果小哥來兩次,我依然付得起很多很多東西,我就能活2*保質期max對趴

　　　　以此類推我們可以發現最初我的錢很多的時候我能活的天數是增加的

　　　　但是!再舉個栗子

　　　　假如我一天點一次外賣,我就會要花很多很多外賣費,活的天數可能更少

　　　　通過這個極端的栗子可以發現,如果我點外賣點的太頻繁,我花的外賣費就很多,能用來買東西的錢就很少辣

　　　　所以它是個單峰函數!

　　　　有點感性,,,?

　　　　那那那講下另一個方法,lzq還港了一個方法,感覺似懂非懂的我大概說下QAQ

　　　　就,我把花費分成兩部分,一部分是快遞費一部分是買東西

　　　　快遞費就分攤到了每一天嘛

　　　　然后我們現在相當于是說要每一天的平均花費min

　　　　那如果我這一輪買的東西多一個

　　　　我的快遞費平攤的對象就+1,同時的我買東西的花費也會增加

　　　　就是從f/i+P/i變成了f/(i+1)+(P+p[i])/(i+1)

　　　　利用反比例函數的性質可以發現開始的時候f/i這個變化值是會很大的,而相對而言的p增加的少一些,所以減少比增加多,它就會是單調增的

　　　　但是到了后期f/i的變化量就很小了嘛,還有一點就是到了后期的pi會很大(因為我們已經是讓p單調增的了

　　　　所以增加的就比減少的多了,所以就成了單調減的

　　　　綜上,它是個單調函數

?

　　但是并不僅僅只要三分那么簡單?? 由于這題的 si 實在是太大了

　　開不了那么大的minn[]和sm[] 所以我們就不能向之前那樣子預處理了

　　每次都要自己計算qwq

　　優秀題解?CODE:

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 typedef long long ll; 5 int n;int cnt;ll m;ll f; 6 struct food 7 { 8 ll cst;ll kep; 9 friend bool operator <(food a,food b){return a.kep<b.kep;} 10 }tp[210],fo[210]; 11 inline ll cost(ll t)//計算存活到t的花費 12 { 13 ll res=0; 14 for(int i=1;i<=cnt;i++) 15 { 16 if(res<0){return -1;} 17 if(t>fo[i].kep){res+=fo[i].cst*fo[i].kep;t-=fo[i].kep;} 18 else {res+=fo[i].cst*t;return res;} 19 }return -1;//這里是避免爆INF 20 } 21 inline ll calcd(ll pm)//計算花多少錢可以存活多少天 22 { 23 ll l=0;ll r=pm; 24 while(l<r)//單調可以二分 25 { 26 ll mid=(l+r+1)/2;ll y=cost(mid); 27 if(y==-1||y>pm){r=mid-1;}else {l=mid;} 28 } 29 return r; 30 } 31 inline ll calct(ll r)//計算T 32 { 33 ll rest=m-r*f;if(rest<0||rest>m){return 0;}//還是避免爆longlong 34 ll pm=rest/r;ll k=calcd(pm);if(k==0){return 0;} 35 ll c2=cost(k+1);ll c1=cost(k);if(c2==-1){return r*k;} 36 else {rest-=c1*r;return rest/(c2-c1)+r*k;} 37 } 38 int main() 39 { 40 scanf("%lld%lld%d",&m,&f,&n); 41 for(int i=1;i<=n;i++){scanf("%lld%lld",&tp[i].cst,&tp[i].kep);} 42 sort(tp+1,tp+n+1);tp[0].kep=-1;fo[0].kep=-1; 43 for(int i=1;i<=n;i++)//單調棧去掉無用的東西 44 {while(cnt!=0&&tp[i].cst<fo[cnt].cst){cnt--;}fo[++cnt]=tp[i];} 45 for(int i=cnt;i>=1;i--){fo[i].kep-=fo[i-1].kep;}//后向差分方便計算 46 ll l=1;ll r=m/f+1;//三分法求函數最值 47 while(r-l>5)//縮小區間 48 { 49 ll x1=l+(r-l)/3;ll x2=l+((r-l)*2)/3; 50 ll y1=calct(x1);ll y2=calct(x2); 51 if(y1<y2){l=x1;}else {r=x2;} 52 } 53 ll res=calct(l);//然后暴力枚舉最大值 54 for(ll i=l+1;i<=r;i++){res=max(res,calct(i));} 55 printf("%lld",res);return 0;//拜拜程序~ 56 } View Code

轉載于:https://www.cnblogs.com/forward777/p/10330727.html

總結

以上是生活随笔為你收集整理的外卖(food) 洛谷4040宅男计划 三分套二分贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。