首页 > 试题广场 >

倒水

[编程题]倒水

热度指数：278 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有一个大水缸，里面水的温度为T单位，体积为C升。另有n杯水（假设每个杯子的容量是无限的），每杯水的温度为t[i]单位，体积为c[i]升。
现在要把大水缸的水倒入n杯水中，使得n杯水的温度相同，请问这可能吗？并求出可行的最高温度，保留4位小数。
注意：一杯温度为t1单位、体积为c1升的水与另一杯温度为t2单位、体积为c2升的水混合后，温度变为(t1*c1+t2*c2)/(c1+c2)，体积变为c1+c2。

输入描述:

第一行一个整数n, 1 ≤ n ≤ 10^5
第二行两个整数T，C,其中0 ≤ T ≤ 10^4, 0 ≤ C ≤ 10^9
接下来n行每行两个整数t[i]，c[i]
0 < t[i], c[i] ≤ 10^4

输出描述:

如果非法，输出“Impossible”（不带引号)否则第一行输出“Possible"（不带引号），第二行输出一个保留4位小数的实数表示答案。

样例解释：往第二杯水中倒0.5升水
往第三杯水中到1升水
三杯水的温度都变成了20

示例1

输入

输出

Possible
20.0000

算法知识视频讲解

C/C++

Hotwill

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <functional>
#include <cmath>
#include <climits>
#include <tuple>
#include <cstdlib>
#include <bitset>
using namespace std;

double get_sum_c(const vector<int> &t, const vector<int> &c, double T, double t0)
{
	double v = 0;
	for (int i = 0; i < t.size() ; i++)
	{
		v += 1.0 * (t[i] - t0) / (t0 - T) * c[i];
	}
	return v;
}

double find_T(const vector<int> &t, const vector<int> &c, double from, double to, double T, double C)
{
	while (true)
	{
		double t0 = (from + to) / 2;
		double k = get_sum_c(t, c, T, t0);
		if (abs(k - C) < 1e-3)
		{
			return t0;
		}
		else if (k < C)
		{
			from = t0;
		}
		else
		{
			to = t0;
		}

		if (abs(from - to) < 1e-12)
		{
			return -1;
		}
	}
}

int main()
{
	int n, T, C;
	cin >> n >> T >> C;

	vector<int> t(n), c(n);
	int max_t = INT_MIN;
	int min_t = INT_MAX;
	for (int i = 0; i < n ; i++)
	{
		cin >> t[i] >> c[i];
		max_t = max(max_t, t[i]);
		min_t = min(min_t, t[i]);
	}



	if (max_t == min_t)
	{
		cout << "Possible" << endl;
		if (T <= min_t)
			printf("%.4f\n", (double)min_t);
		else
		{
			double k = find_T(t, c, max_t, T, T, C);
			if (k == -1)
			{
				cout << "Impossible" << endl;
			}
			else
			{
				cout << "Possible" << endl;
				printf("%.4f\n", (double)k);
			}
		}
	}
	else if (T <= min_t)
	{
		if (get_sum_c(t, c, T, min_t) <= C)
		{
			cout << "Possible" << endl;
			printf("%.4f\n", (double)min_t);
		}
		else
		{
			cout << "Impossible" << endl;
		}
	}
	else if (T >= max_t)
	{
		double k = find_T(t, c, max_t, T, T, C);
		if (k == -1)
		{
			cout << "Impossible" << endl;
		}
		else
		{
			cout << "Possible" << endl;
			printf("%.4f\n", (double)k);
		}
	}
	else
	{
		cout << "Impossible" << endl;
	}

	return 0;
}

发表于 2017-06-19 19:46:17 回复(0)

阿破

#include"bits/stdc++.h"
using namespace std;
int n;
double T,C;
bool ok=0;
double min(double x,double y){
    return x<y?x:y;
}
double max(double x,double y){
    return x>y?x:y;
}
bool check(double mid,vector<double>&c,vector<double>&t,double CC){
    for(int i=0;i<n;i++){
        double water=(c[i]*mid-c[i]*t[i])/(T-mid);
        if(mid<min(t[i],T))return 1;//温度太低
        else if(mid>max(t[i],T)) return 0;//温度太高
        if(water>CC){//水不够 
            if(mid<T)return 0;//温度太高 
            if(mid>T)return 1;//温度太低
        }
        CC-=water;
    }
    ok=1;
    return 1;
}
int main(){
    cin>>n;
    cin>>T>>C;
    vector<double>t(n),c(n);
    double l=T,r=T;
    
    for(int i=0;i<n;i++){
        cin>>t[i];
        cin>>c[i];
        l=min(l,t[i]);
        r=max(r,t[i]);
    }
    while(l<=r){
        double mid=(l+r)/2.0;
        if(check(mid,c,t,C)){//mid温度太低或者正常
            
            l=mid+0.00001;
        }
        else{
            r=mid-0.00001;
        }
    }
    if(!ok){
        cout<<"Impossible";
    }
    else{
        cout<<"Possible"<<endl;
        printf("%.4f",r);
    }
}

编辑于 2021-02-24 15:45:15 回复(0)

C/C++

DustinJ

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
int main()
{
    int n,T,C;
    while(cin>>n>>T>>C){
        int tmp1,tmp2;
        int min=10000,max=0;
        double sum=0,Csum=0;
        for(int i=0;i<n;i++){
            cin>>tmp1>>tmp2;
            if(tmp1<min){
                min=tmp1;
            }
            if(tmp1>max){
                max=tmp1;
            }
            sum+=tmp1*tmp2;
            Csum+=tmp2;
        }
        sum+=(double) T*C;
        Csum+=(double) C;
        double Tmix=sum/Csum;
        if(Tmix>max){
            cout <<"Possible"<<endl;
            cout<<setprecision(4)<<fixed<<Tmix;
        }else if(Tmix<=min){
            cout <<"Possible"<<endl;
            cout<<setprecision(4)<<fixed<<double(min);
        }else{
            cout <<"Impossible"<<endl;
        }
    }
    return 0;
}

编辑于 2017-06-27 11:10:20 回复(0)