首页 > 试题广场 >

降温（easy）

[编程题]降温（easy）

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

天气开始降温了。

如果某一天的温度比前一天降低的值不小于 $x$ ，小红就会认为这是一场“寒潮”。
现在给定了每天的气温，但有一些日子的气温是未知的。小红想知道，发生寒潮的次数的最大值和最小值是多少？
注：我们认为，每天气温的值域一定在[-50,50]。

输入描述:

第一行输入两个正整数，代表总天数、以及寒潮的判定标准。
第二行输入个整数，代表每天的气温。特殊的，如果为-999，代表这一天的气温是未知的。


或者

输出描述:

两个整数，代表寒潮数量的最大值和最小值。

示例1

输入

3 10
50 -999 -50

输出

2 1

说明

第二天的气温未知，若这一天的气温在[41,50]或者[-50,-41]，则共有1天寒潮；否则是两天寒潮。

示例2

输入

4 100
-999 -999 -999 -999

输出

2 0

说明

当且仅当四天的气温为50,-50,50,-50时才会有2天寒潮。

算法知识视频讲解

渔火江枫_00911

贪心法可解

以下以[-999, 20, -999, -999, 5, -999]，寒潮阈值为5为例
最小化天数策略：两端缺失值保持与最接近两端的非缺失值20和5一致，而20和5隔3天，平均一天降温达到5
怎么办，答案是长痛不如短痛——[20, 20, 5, 5, 5, 5]，降温一步到位，最小值1天
最大化策略：注意到气温上下限为-50到50，先贪心法制造寒潮，每天都比前一天降5，你说触底-50了怎么办，直接再拉到50继续，这叫做平地起风雷

发表于 2025-12-07 10:28:04 回复(1)

Reisentyan

今天百度之星打铁了，很不开心！

我们将使用拉马努金瞪眼法来解决这个问题

我们发现：寒潮的定义为 $a[i]-a[i+1]>=x$

也就是说，升温是不算寒潮的

对于最少寒潮次数来说，需要你填的数字，你只要把前一天的温度降低x-1度就好了

如果温度降到-50度以下了，那就填-50度好了

因为如果某一位不需要你填了，你前面填的温度是无法改变后面的状态的

换句话说：“活在当下好了”

这就是一种贪心的策略

如果是求最多寒潮次数呢，那就把前一天的温度降低x度就好了，刚好可以算作一次

如果降到-50度以下了，那无论如何这一位都不可能累加答案了，之间设成50度，给下一位留出累加答案的可能

注意到，代码要写成这样：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n =0;int x =0;
    cin>>n>>x;
    vector<int>a(n+1,0);
    vector<int>maxx(n+1,0);
    vector<int>minn(n+1,0);
    for(int i =1;i<=n;i++)cin>>a[i];
    a[0] = a[1];
    int mxnow = a[0];
    int minow = a[0];
    for(int i =1;i<=n;i++)
    {
        if(a[i]!=-999)
        {
            minow = mxnow = a[i];
        }
        else
        {
        if(mxnow-x<-50)mxnow = 50;
        else mxnow = mxnow-x;
        minow = max(-50,minow-x+1);
        }
        maxx[i] = mxnow;
        minn[i] = minow;
    }
    int mxans=0,mnans=0;
    for(int i = 1;i<n;i++)
    {
        if(maxx[i]-maxx[i+1]>=x)mxans++;
        if(minn[i]-minn[i+1]>=x)mnans++;
        //cout<<maxx[i]<<' ';
    }
    cout<<mxans<<' '<<mnans<<endl;

}
/*
⡀⠎⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣄⠃⠈⣶⡛⠿⠭⣉⠛⠿⡿⠛⠉⣀⣠⣤⣭⡏⠴⢀⣴⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣷⣱⣬⠛⠉⠀⠀⢠⠀⠀⠀⢀⣀⠀⠉⠿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠈⡿
⠀⠀⠀⠀⠀⠀⠀⢀⢿⣿⣿⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⡏⠀⠀⠀⠀⠈⠳⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⠋⠀⣇⠀⠀⠀⠀⠀⠀⠀⠀⠈
⠀⠀⠀⠀⠀⠀⠀⣸⠀⣿⣿⣿⣿⠟⠀⠀⠀⠂⠀⠀⢠⠀⠀⠀⠀⠀⠀⠀⠈⡀⠀⠀⠀⠻⣿⣿⣿⣿⣷⡀⠘
⠀⠀⠀⠀⠀⠀⠀⣧⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠙⣿⣿⣿⣿⣿⣄⣧
⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⠀⠀⠀⠀⠈⢿⣿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⢂⠻⣿⣿⣿⣿⣿⣄
⠀⠀⠀⠀⠀⣿⣿⣿⣿⣹⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣇⠀⠀⠀⠀⠀⡄⠈⢿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⣿⣿⣿⣿⠁⡇⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀⠐⠸⠀⠀⠻⣿⣿⣿⣆⢦
⠀⠀⢠⣿⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⣼⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡏⣧⠀⠀⠀⠀⠐⣇⠀⠀⠙⣿⣿⣿⡄⠙⣄
⠀⣴⣿⣿⣿⣿⠏⠀⢸⠀⠀⠀⠀⠀⠀⡿⢿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣃⣈⣦⠀⠀⠀⠀⢹⠀⠀⠀⠸⣿⣿⣿⠀⠀⠳⣀
⠋⣸⣿⣿⣿⡟⠀⠀⠀⡆⠀⠀⠀⠀⠀⡏⠙⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠀⢠⠀⠀⠀⢧⠀⠀⠀⠀⡇⠀⠀⠀⠘⣿⣿⣷⠀⠀⠘
⠀⣿⣿⣿⢩⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⣀⠀⢱⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠂⢀⣴⣶⣿⣿⡀⠀⠀⢻⠀⠀⠀⠀⠹⣿⣿⡄
⢸⣿⣿⠃⠈⠀⠀⢸⠀⣿⣆⠀⠀⠀⠀⣿⣿⣿⠷⠘⡀⠀⠀⠀⠀⠀⠀⢠⢹⡀⠈⡿⠻⣿⣛⢿⣿⣷⡀⠈⠀⠀⠀⠀⠀⢻⣿⣿
⣿⣿⣿⠀⠀⠀⠀⢸⠀⡇⣼⣄⠀⠀⠀⢻⣿⡄⠑⠑⣿⡀⠀⠀⠀⢀⠀⠂⠇⠀⠀⠖⠛⢿⣿⣿⣌⢿⣿⣿⡆⠀⠀⠀⠀⠀⣿⣿⡀
⣿⣿⡇⠀⠀⠀⠀⢸⠀⣾⣿⣿⡷⠿⣷⣤⣿⣿⡄⠀⠀⠀⠑⠤⡀⠀⠃⠀⠀⠀⠀⣿⣶⣿⣿⣿⣿⣆⠙⣿⣧⠀⠀⠀⠀⠀⣿⣿⡇
⣿⣿⠁⠀⠀⠀⠀⠘⣾⣿⣿⠁⣴⣿⣿⣿⣿⣿⣇⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠸⡏⠙⣿⠉⠻⣿⠀⠀⣿⠀⠀⠀⣄⠀⣿⢸⣷
⣿⣿⡇⠀⠀⠀⠀⠀⣿⣿⠁⠀⣿⣿⠋⣿⠏⠙⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⢀⢻⠀⠀⢀⡟⢀⣿⣸⢃⠟
⣿⣿⣿⠀⡄⠀⠀⠀⠘⠻⡄⠀⢹⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡘⠀⢀⣿⠃⣿⣿⡗⠁
⣧⣿⣿⣧⢹⡀⠀⠀⠀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⣴⣿⣿⣾⣿⣿⣿
⢿⠘⣿⣿⣿⣿⣤⠀⠢⡀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣵⣿⣿⣿⣿⣿⣿⣿⣿⣷
⠀⠉⣿⣿⣿⡿⣿⠻⣷⣬⣓⣬⣄⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠉⠈⠈⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⠃⠼⢉⣿⣿⣿⣿⣿⣿⣿
⠀⠀⣿⣿⣿⣷⠀⠀⠀⠘⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⡏⠀⠀⢸⠀⢻⢿⣿⣿⡏⣿
⠀⢸⣿⣿⣿⣿⠀⠀⠀⠀⢻⣿⣿⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⣾⣿⣿⣿⣿⠀⠀⠀⢸⠀⠀⢸⣿⣿⠘⡀
⢦⡿⣿⣿⣿⢿⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣶⣶⣦⡄⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠘⡄⠀⠈⣿⣿⡄⠱
⣴⠛⣾⣿⣿⢸⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⡄⠀⠀⠀⠀⠀⠀⠀⣯⠛⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⣇⠀⠀⣿⣿⣿
⠿⠀⣿⣿⣿⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⠟⠰⡾⠃⠀⠀⠀⠀⠀⠀⠀⠙⡟⠀⢻⣿⣿⣿⣿⣿⡆⠀⠀⠀⠸⠀⠀⠸⣿⣿⣷
⠆⢳⣿⣿⡇⠀⠀⠀⠀⠀⠀⣿⣿⣿⠛⠿⠿⢿⡟⠀⠀⠉⠦⣀⡤⢶⠀⠖⠲⠶⠊⠀⠀⠀⢻⡛⠛⠛⣿⣿⠀⠀⠀⠀⠃⠀⠀⢿⣿⣿
*/

发表于 2025-12-07 23:04:54 回复(0)

想回家的小白在思考

小白第一次写题解，这里应该算是用了贪心？

#include <stdio.h>
int a[105];
int a_cp[105];
int main() {
    int n, x;
    scanf("%d%d", &n, &x);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    a[0] = -50, a[n+1] = 50;
    for(int k = 0; k <= n+1; k++) a_cp[k] = a[k]; //复制数组
    
    for(int j = 1; j <= n; j++){  
        if(a[j] == -999){
            if(a[j-1] - x < -50) a[j] = 50;
            else a[j] = a[j-1] - x;
        }
    }//最大的情况

    for(int j = 1; j <= n; j++){
        if(a_cp[j] == -999){
            if(a_cp[j-1] - x < -50) a_cp[j] = -50;
            else a_cp[j] = a_cp[j-1] - x + 1;
        }
    }//最小
    
    int max = 0, min = 0;
    for(int i = 1; i <= n; i++) if(a[i] - a[i+1] >= x) max++;
    for(int i = 1; i <= n; i++) if(a_cp[i] - a_cp[i+1] >= x) min++;
    printf("%d %d\n", max, min);

    return 0;
}

欢迎讨论交流，指正错误！

发表于 2025-12-07 22:41:14 回复(0)

提交观点

问题信息

难度：

3条回答 6收藏 15浏览

降温（easy）

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题