題目鏈接：點(diǎn)擊查看

題目大意：一杯熱水的溫度為 h ，一杯涼水的溫度為 c ，現(xiàn)在有一個(gè)空桶，要求輪流執(zhí)行以下操作：

倒一杯熱水

倒一杯涼水

倒一杯熱水

.....

每次總是以一杯熱水開(kāi)始，問(wèn)需要倒多少倍水，才能使得桶內(nèi)的平均溫度與 t 之差最小

題目分析：數(shù)學(xué)不好，推不出來(lái)答案的表達(dá)式，所以當(dāng)三分來(lái)做了，首先熱水和涼水的相對(duì)狀態(tài)只有兩種情況：

熱水和涼水一樣多

熱水比涼水多一杯

然后再設(shè)平均值 ave = ( h +?c ) / 2 ，然后需要再分兩種情況：

t = ave：答案為 2

t < ave：需要涼水多一杯

t > ave：需要熱水多一杯

上面的第二種情況是不合法的，所以對(duì)于第二種情況來(lái)說(shuō)，最優(yōu)的情況就歸納于情況一中了，換句話說(shuō)當(dāng) t <= ave 時(shí)，答案都為 2

這樣我們只需要三分出熱水比涼水多一杯時(shí)的最優(yōu)解就好了，因?yàn)槭钦麛?shù)的三分，可以將范圍擴(kuò)大點(diǎn)，然后再暴力找最小值

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;int h,c,t;double cal(LL n) {return fabs(1.0*(n*h+(n-1)*c)/(2*n-1)-t); }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false); int w;cin>>w;while(w--){scanf("%d%d%d",&h,&c,&t);if(h==t){puts("1");continue;}if(h+c>=t*2){puts("2");continue;}int l=1,r=inf;while(r-l>10){LL mid=l+r>>1;LL mmid=r+mid>>1;if(cal(mid)<cal(mmid))r=mmid;elsel=mid;}double eps=1e10;LL ans=0;for(LL i=l;i<=r;i++){if(eps>cal(i)){eps=cal(i);ans=i;}}printf("%lld\n",ans*2-1);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1359C Mixing Water(三分)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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