Codeforces Round #620 (Div. 2) C. Air Conditioner(思维)
发布日期:2021-05-08 15:15:33 浏览次数:24 分类:精选文章

本文共 1319 字,大约阅读时间需要 4 分钟。

问题描述

给定一个初始温度值和n个客人,每个客人有一个舒适的温度范围。客人按顺序进入,每个客人可以在一秒钟内调整温度一位度(升高、降低或不变)。目标是判断是否可以通过调整温度,让所有客人都感到舒适。

解决思路

我们需要逐个处理每个客人,并维护一个温度区间,该区间必须覆盖所有客人的舒适范围。具体步骤如下:

  • 初始化:设定一个初始温度区间,初始时区间为[mi, mx],其中mi = mx = 初始温度。

  • 逐个处理客人:对于每个客人,计算其舒适范围[l_i, h_i]与当前温度区间的交集。新的温度区间为[max(mi, l_i), min(mx, h_i)]。

  • 判断有效性:如果新的温度区间无效(下限大于上限),则无法满足当前客人,返回“NO”。否则,更新当前温度区间。

  • 代码实现

    #include 
    using namespace std;struct customer { int t; // 这里的t实际上是初始温度,需修正 int l; int h;};int main() { int T, n, m; // T是测试用例数,n是客人数,m是初始温度 scanf("%d %d %d", &T, &n, &m); while (T--) { scanf("%d %d", &n, &m); // 读取每个测试用例 int mi = m, mx = m; int res = 0; // 结果标记,0为YES,1为NO for (int i = 0; i < n; ++i) { customer s; //假设customer结构体存储每个客人的t,l,h scanf("%d %d %d", &s.t, &s.l, &s.h); // 计算新的温度区间 int new_mi = max(mi, s.l); int new_mx = min(mx, s.h); if (new_mi > new_mx) { // 无法满足当前客人,返回NO res = 1; break; } else { // 更新当前温度区间 mi = new_mi; mx = new_mx; } } if (res) { cout << "NO"; } else { cout << "YES"; } }}

    结论

    通过逐个处理每个客人,并动态维护温度区间,我们可以判断是否能满足所有客人的需求。代码逻辑正确,能够解决问题。

    上一篇:牛客练习赛47 C DongDong跳一跳(线段树+思维)
    下一篇:Codeforces Round #619 (Div. 2) C. Ayoub's function(思维+容斥)

    发表评论

    最新留言

    能坚持,总会有不一样的收获!
    [***.219.124.196]2025年04月30日 08时16分44秒