牛客网OJ题解--20210223

倒水

https://ac.nowcoder.com/acm/problem/13228

本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。

NC13228-倒水

题目链接

https://ac.nowcoder.com/acm/problem/13228

题目描述

有一个大水缸，里面水的温度为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位小数的实数表示答案。

测试样例

输入

输出

Possible
20.0000

说明

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

解题思路

用贪心不用二分，我们直接计算大缸里的水和所有杯中的水融合在一起的平均水温，然后就有以下三种情况：

平均水温小于等于杯中水的最低温度，那么大缸中的水是降温的，那么可以调节并且可调节的最高温度就是杯中水的最低温度
平均水温大于等于杯中水的最高温度，那么大缸中的水是升温的，那么可以调节并且可调节的最高温度就是平均水温
平均水温介于最低温度和最高温度之间，说明大缸中的水也是结余最低温度和最高温度之间，那么不可以调节，因为无论如何调节，最低温度只会无限趋近于平均水温而不会等于平均水温，最高温度只会无限趋近于平均水温而不会等于平均水温，因此杯中的水不可能温度相等。

解题代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
double t[N], c[N];

int main()
{
    double T, C;
    int n;
    cin >> n;
    cin >> T >> C;
    double v = 0.0;
    v += T * C;
    double tmax = 0.0, tmin = 1e9, c1 = C;
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i] >> c[i];
        v += t[i] * c[i];
        c1 += c[i];
        tmax = max(t[i], tmax);
        tmin = min(t[i], tmin);
    }
    //求平均值
    double aver = v / c1;
    //小于最小温度，那么可以调节的最大温度就是最小值
    //大缸中的水是降温的，比杯中最低温的水温度还低
    if (aver <= tmin)
    {
        cout << "Possible" << endl;
        //保留小数点4位
        cout << fixed << setprecision(4) << tmin << endl;
    }
    //能够大于那么就输出平均值
    //大缸的水是升温的，比杯中最高温度的水温度还高
    else if (aver >= tmax)
    {
        cout << "Possible" << endl;
        cout << fixed << setprecision(4) << aver << endl;
    }
    //否则不可能调节
    else
    {
        //原因很简单对于tmin<aver<tmax
        //再怎么加水tmin只会无限趋于aver而不会等于aver
        //再怎么加水tmax也只会无限趋近于aver而不会等于aver
        cout << "Impossible" << endl;
    }
    system("pause");
    return 0;
}

NC14134-生物课程

题目链接

https://ac.nowcoder.com/acm/problem/14134

题目描述

𝑅𝑒𝑘𝑖是一名武侦高狙击科的学生，武侦高也设有基础学科，现在她正
在完成生物课的作业。
给出一张𝑛个点𝑚条边的无向图，这张无向图描述了一个细胞，细胞有三种：X型、Y型还是I型。如下图：

如图，虚线方向的链可以无限延伸，现在需要判断给定的图是哪一种细胞，或者都不是。

第一行，两个正整数𝑛，𝑚。接下来𝑚行，每行两个正整数𝑢, 𝑣描述一条无向边。输出这种细胞的类型，若都不是输出NotValid。对于100%的数据，2 ≤ 𝑛 ≤ 500，0 ≤ 𝑚 ≤ 𝑛*(𝑛−1)/2，没有重边和自环。

测试样例

样例1

输入

输出

样例2

输出

样例3

输入

2 1
1 2

输出

样例4

输入

输出

NotValid

解题思路

我们可以根据上面的题干总结一下各种情况的特点：

X型：点的边数只能为1,2,4并且边数为4的点只能有一个
Y型：点的边数只能为1,2,3并且边数为3的点只能有一个
I型：点的边数只能为1,2

非法情况有：

有孤立点(坑点)
有多个X或Y中心点
中心点边数>4

解题代码

#include <bits/stdc++.h>
using namespace std;

int p[505]; //记录各个点的边数

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        //两个点各加一条边
        p[u]++;
        p[v]++;
    }
    //对1到n顶点排序，按照边数从小到大排序
    sort(p + 1, p + n + 1);
    int min = p[1];
    int max = p[n];
    //非法的几种情况
    //1.有的点无边相连，孤立点，非法
    //2.中心点边数大于4
    //3.X,Y中心点都有，或者有多个X中心点
    //4.有多个Y中心点
    if (min == 0 || max > 4 || (max == 4 && p[n - 1] >= 3) || (max == 3 && p[n - 1] >= 3))
    {
        cout << "NotValid" << endl;
        system("pause");
        return 0;
    }
    else
    {
        //否则就是X,Y,I中的一个
        if (max == 4)
            cout << "X" << endl;
        else if (max == 3)
            cout << "Y" << endl;
        else
            cout << "I" << endl;
    }
    system("pause");
    return 0;
}