您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 1492 Up and Down Sequences：模擬統計上升/下降段平均長度

編輯：關於C++

題目大意

輸入一個整數序列（以 0 結束，多組數據），統計序列中非嚴格遞增段和非嚴格遞減段的平均長度。長度至少為 2 的段才計入。

算法邏輯

掃描序列，識別單調段：

上升段：a[i] ≤ a[i+1] 連續
下降段：a[i] ≥ a[i+1] 連續
平段（相等）：同時屬於上升和下降，需特殊處理避免重複計數

完整代碼

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

int a[64], n;

void process() {
    int up = 0, down = 0, upSum = 0, downSum = 0;
    for (int i = 1; i < n; ) {
        if (a[i] < a[i+1]) {  // 上升段
            ++up;
            int j = i+1;
            for (; j <= n && a[j-1] <= a[j]; ++j) ++upSum;
            i = j-1;
        }
        else if (a[i] > a[i+1]) {  // 下降段
            ++down;
            int j = i+1;
            for (; j <= n && a[j-1] >= a[j]; ++j) ++downSum;
            i = j-1;
        }
        else {  // 相等：向前看決定歸屬
            int flag = 0, j = i+1;
            for (; j <= n; ++j) {
                if (a[j-1] < a[j]) { flag = 1; break; }  // 後面上升
                if (a[j-1] > a[j]) { flag = -1; break; } // 後面下降
            }
            if (flag == 0) break;  // 全相等，結束
            if (flag == 1) {  // 歸入上升
                ++up;
                for (; j <= n && a[j-1] <= a[j]; ++j) ++upSum;
            } else {  // 歸入下降
                ++down;
                for (; j <= n && a[j-1] >= a[j]; ++j) ++downSum;
            }
            i = j-1;
        }
    }
    double avgUp = upSum ? (double)upSum / up : 0;
    double avgDown = downSum ? (double)downSum / down : 0;
    printf("Nr values = %d: %.6lf %.6lf\n", n, avgUp, avgDown);
}

int main() {
    n = 0;
    while (true) {
        int x; scanf("%d", &x);
        if (x == 0) {
            if (n == 0) break;  // 雙 0 結束所有輸入
            process();
            n = 0;
        } else {
            a[++n] = x;
        }
    }
    return 0;
}