C. Mixing Water（三分）

题：https://codeforces.com/contest/1359/problem/C

题意：对于一个容器，每次能往里面倒一瓶水，热水和冷水交替倒，最少倒入一瓶水，容器水的温度等于总体的平均温度，给定温度 t ，问最少倒几瓶水最终容器中水的温度能最接近温度t

分析：这个问题可以二分三分解，关键看你怎么写check函数，这里只讲三分，对于倒入的杯数x关于温度T的函数的递减的，那么t-T函数就是一个抛物线，所以用三分解决。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e6+6;
const ll inf=0x3f3f3f3f;
int h,c,t;
double check(ll x,ll y){
    return fabs((double)t-1.0*(x*h+y*c)/(x+y));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){

        cin>>h>>c>>t;
        if(h+c>=2*t){
            cout<<2<<endl;
        }
        else{
            ll l=0,r=inf,lmid,rmid;
            while(l<r){
                lmid=l+((r-l)/3);
                rmid=r-((r-l)/3);
                if(check(lmid+1,lmid)<=check(rmid+1,rmid))
                    r=rmid-1;
                else
                    l=lmid+1;
            }cout<<2*l+1<<endl;
        }

    }
    return 0;
}

View Code

原文链接: https://www.cnblogs.com/starve/p/12994654.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/351866

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

C. Mixing Water（三分）

相关推荐