Problem #25 - ECNU Online Judge

Chains.Z

4 年，8 月前

我觉得这道题其实很好理解，假如给的温度是15度，数据是两个up，300个down，如果你单纯的

if(order == "DOWN")
                temper -= 0.1;
            else
                temper += 0.1;

这样temper肯定会小于0，那应该怎么办呢？————只要在最后一个up的时候把temper改成30就可以了，因为题目说了一定有解，所以不可能出现301个down
那么，接下来的代码理解起来就很简单了

#include <iostream>
#include <string>
using namespace std;
int main(){
    double temper;int __;string order;
    cin >> temper;cin >> __;cin >> order;
    for (int _ = 0; _ < __; _++){
        string next_order;
        if (cin >> next_order){
            if (next_order == order){
                if(order == "DOWN")
                    temper -= 0.1;
                else
                    temper += 0.1;
            }
            else{
                if(next_order == "DOWN")
                    temper = 30.0;
                else
                    temper = 0.0;
            }
            order = next_order;
        }
        else{
            if(order == "DOWN")
                temper -= 0.1;
            else
                temper += 0.1;
        }
        printf("%.1lf\n",temper);
    }
}

PS：涉及到浮点数输出的时候cout是真滴麻烦，这题如果用cout输出长这个样子cout << fixed << setprecision(1) << temper << endl;

回复 1 0

Master X

6 年，8 月前

瞎猜都能过的题……

回复 0 0

Fifnmar

4 年，10 月前

这道题因为数据有点弱，其实瞎猜一个比较中间的数值也可以过。

下面是正经做法，不过不一定是最优做法。

分析每次猜测天气的限制，也就是那个 $0\leq T\leq 30.0$，可知问题在于确定每次温度上升或下降的步长。容易想到，可以假设每次都改变最小步长，即 0.1，但这样可能出现出界问题。为此需要在前面某一次变化中做出补偿。举个例子，如果某次变化后温度变成了 -0.1，说明前面某处 UP 需要上升 0.2 度。

我的意思是先假定每次都以最小步长改变，发现出界问题就回头改变。改变哪一个呢？改变第一个可以改的地方可能导致前面某处本来不越界的位置越界。应该改最后一次反向变化的位置。

这个想法没有验证过，或许改第一个也可以？我直觉上觉得不可以。

这样总得来看解决步骤分两步：
1. 调整步长；
2. 输出

下面是代码：

#include <iostream>
#include <string>
using namespace std;

int t, n;
int variation[1001];

inline bool overflow(int res) noexcept { return res < 0 || res > 300; }

void solve() {
    // #1 adjust variation;
    int res = t;
    for (int i = 0; i < n; ++i) {
        res += variation[i];
        if (overflow(res)) {
            if (res < 0) {
                // need up-compensation;
                int j = i - 1;
                for (; variation[j] < 0; --j)
                    ;
                ++variation[j];
                res = 0;
            } else {
                // needs down-compensation;
                int j = i - 1;
                for (; variation[j] > 0; --j)
                    ;
                --variation[j];
                res = 300;
            }
        }
    }

    // #2 Output;
    res = t;
    for (int i = 0; i < n; ++i) {
        res += variation[i];
        printf("%d.%d\n", res / 10, res % 10);
    }
}

int main() {
    double temp;
    cin >> temp >> n;
    t = temp * 10;
    for (int i = 0; i < n; ++i) {
        string a;
        cin >> a;
        variation[i] = a == "UP" ? 1 : -1;
    }
    solve();
}