贪心算法--牛客倒水
标题:贪心
链接:https://ac.nowcoder.com/acm/problem/13228
来源:牛客网
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld
题目描述
有一个大水缸,里面水的温度为T单位,体积为C升。另有n杯水(假设每个杯子的容量是无限的),每杯水的温度为t[i]单位,体积为c[i]升。
现在要把大水缸的水倒入n杯水中,使得n杯水的温度相同,请问这可能吗?并求出可行的最高温度,保留4位小数。
注意:一杯温度为t1单位、体积为c1升的水与另一杯温度为t2单位、体积为c2升的水混合后,温度变为(t1c1+t2c2)/(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
输入:
3
10 2
20 1
25 1
30 1
输出:
Possible
20.0000
思路:
先根据温度排个序,把所有的水混一块后的温度求出。
再分三种情况:
第一种:如果加的水的温度小于最低温度,
第二种:如果加的水的温度大于最高温度
第三种:位于两者之间,则不可能达到同一温度
温度升高,比T低的永远也比它低,比它高的永远也比它高,因此第一种情况不可能成立,只能无限接近不能达到一致
sort函数用法:sort函数用法
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
double tc,C;
ll m;
struct node
{
double t,c;//c是容积,t是温度
bool operator<(const node &rh)const
{
return t<rh.t;
}//定义优先级
}p[10010];
int main()
{
ll sum=0,sumc=0;
cin>>m;
cin>>tc>>C;
sum+=tc*C;
sumc+=C;
for(int i=1;i<=m;i++)
{
cin>>p[i].t>>p[i].c;
sum+=p[i].t*p[i].c;
sumc+=p[i].c;
}
double ans=sum*1.0/sumc;//将所有水混一块 后的温度
sort(p+1,p+1+m);//排序
if(tc<p[m].t&&tc>p[1].t)//如果位于中间的话,则不可能
{
cout<<"Impossible";
}
else if(p[m].t<=tc)//如果tc的温度大于最高温度,则证明之能升温
{
if(p[m].t<=ans)printf("Possible\n%.4lf",ans);//如果可以,输出最高温度
else
{
cout<<"Impossible";
}
}
else //如果tc的温度小于最低温度,只能降温
{
if(ans<=p[1].t)printf("Possible\n%.4lf",p[1].t);//如果最后的温度小于第一个温度则证明可以达到同一温度
else
{
cout<<"Impossible";
}
}
return 0;
}
上一篇: Java文件操作小结
下一篇: LeeCode3:无重复字符的最长子串
推荐阅读