CodeForces - 1359C Mixing Water(三分)

题目链接：点击查看

题目大意：一杯热水的温度为 h ，一杯凉水的温度为 c ，现在有一个空桶，要求轮流执行以下操作：

倒一杯热水

倒一杯凉水

倒一杯热水

.....

每次总是以一杯热水开始，问需要倒多少倍水，才能使得桶内的平均温度与 t 之差最小

题目分析：数学不好，推不出来答案的表达式，所以当三分来做了，首先热水和凉水的相对状态只有两种情况：

热水和凉水一样多

热水比凉水多一杯

然后再设平均值 ave = ( h + c ) / 2 ，然后需要再分两种情况：

t = ave：答案为 2

t < ave：需要凉水多一杯

t > ave：需要热水多一杯

上面的第二种情况是不合法的，所以对于第二种情况来说，最优的情况就归纳于情况一中了，换句话说当 t <= ave 时，答案都为 2

这样我们只需要三分出热水比凉水多一杯时的最优解就好了，因为是整数的三分，可以将范围扩大点，然后再暴力找最小值

代码：
 

#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; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1359C Mixing Water(三分)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。