1128: 出租車費(fèi)
時(shí)間限制: 1 Sec 內(nèi)存限制: 32 MB
提交: 871 解決: 299
[提交][狀態(tài)][討論版][命題人:外部導(dǎo)入]

題目描述
某市出租車計(jì)價(jià)規(guī)則如下：起步4公里10元，即使你的行程沒(méi)超過(guò)4公里；接下來(lái)的4公里，每公里2元；之后每公里2.4元。行程的最后一段即使不到1公里，也當(dāng)作1公里計(jì)費(fèi)。
一個(gè)乘客可以根據(jù)行程公里數(shù)合理安排坐車方式來(lái)使自己的打車費(fèi)最小。
例如，整個(gè)行程為16公里，乘客應(yīng)該將行程分成長(zhǎng)度相同的兩部分，每部分花費(fèi)18元，總共花費(fèi)36元。如果坐出租車一次走完全程要花費(fèi)37.2元。
現(xiàn)在給你整個(gè)行程的公里數(shù)，請(qǐng)你計(jì)算坐出租車的最小花費(fèi)。

輸入
輸入包含多組測(cè)試數(shù)據(jù)。每組輸入一個(gè)正整數(shù)n（n<10000000），表示整個(gè)行程的公里數(shù)。
當(dāng)n=0時(shí)，輸入結(jié)束。

輸出
對(duì)于每組輸入，輸出最小花費(fèi)。如果需要的話，保留一位小數(shù)。

樣例輸入
3
9
16
0
樣例輸出
10
20.4
36
分析：最小花費(fèi) 考慮dp或貪心
從1往后寫(xiě)會(huì)發(fā)現(xiàn) 這個(gè)問(wèn)題最小花費(fèi)有區(qū)間規(guī)律 每8個(gè)里程會(huì)來(lái)個(gè)循環(huán) 最后余下的如果多于4 那么就重新打個(gè)車計(jì)費(fèi) 如果少于4 就按照原2.4元車費(fèi)計(jì)費(fèi)比較省錢
所以這里就相當(dāng)于直接取局部最優(yōu)就等于全局最優(yōu)了
整個(gè)規(guī)則適用于任意n情況 因?yàn)檫@個(gè)每四個(gè)2.4所省下的0.4元都可以被一個(gè)2.4-2 = 0.4 給平均掉
而后者的計(jì)費(fèi)方式后四個(gè)都是每公里2元 跟一路2.4元下來(lái)有直觀的差距
所以每個(gè)輸入n都取決于相同的規(guī)則判斷
故局部的規(guī)則最優(yōu)就等于全局的最優(yōu)
所以即便是最優(yōu)問(wèn)題 也可能從中找出規(guī)律 然后按照規(guī)律貪心解之。

#include<cstdio> #include<cstring> #include<iostream> #include<map> #include<cmath> #include<windows.h> #include<algorithm> #include<set> const double eps = 1e-1; using namespace std; typedef long long ll; int main(){int n;while(scanf("%d",&n),n){double sum=0;if(n<=4)puts("10");else{sum=(n/8)*18 + (n%8!=0?( n%8>4? (10 + (n%4) * 2): (2.4*(n%4==0?4:(n%4)))):0);if(sum-(int)sum>eps)printf("%.1f\n",sum);else printf("%d\n",(int)sum);}}return 0; }

ps：這應(yīng)該是我寫(xiě)過(guò)的最長(zhǎng)的條件表達(dá)式了。。。

總結(jié)

以上是生活随笔為你收集整理的codeup 1128: 出租车费 贪心|找规律的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。