欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

贪心算法--牛客倒水

程序员文章站 2022-07-12 12:16:16
...

标题:贪心

链接: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;
}
相关标签: 贪心 贪心算法