1260 Sales

題目連結

題目敘述

CozyWalk 公司 CEO Cooper 先生，自公司成立起每天都會收到當天的銷售報告。從公司成立的第二天起，他會將當天的報告與之前所有的報告進行比較，計算出那些銷售額小於或等於當天銷售額的天數。獲得這個數值後，他會將其記錄在一個列表中。

這個問題可以更正式地表述如下： 設 A = (a₁, a₂, ..., aₙ) 為每天的銷售額列表。Cooper 先生會維護另一個整數列表 B = (b₁, b₂, ..., bₙ₋₁)，每個值代表滿足條件的前幾天數量。在第 i 天 (2 ≤ i ≤ n)，他會計算 bᵢ₋₁，它是滿足 ak ≤ aᵢ 的 ak 的數量，其中 1 ≤ k < i。

例如，假設 A = (20, 43, 57, 43, 20)。第四天的銷售額 a₄ = 43，比它小或等於的前幾天銷售額有 a₁ ≤ a₄, a₂ ≤ a₄，a₃ > a₄，因此有 2 天符合條件，因此 b₃ = 2。類似地，可計算出 b₁, b₂ 和 b₄，結果為 B = (1, 2, 2, 1)。

給定一個大小為 n 的銷售額列表 A，請寫一個程式輸出列表 B 中 n - 1 個整數的總和。

輸入格式

你的程式需從標準輸入讀取資料。輸入包含 T 組測試資料。第一行為整數 T，代表測試資料組數。每組測試資料以一行整數 n 開始，代表 A 的長度 (2 ≤ n ≤ 1000)。接著一行有 n 個整數 aᵢ (1 ≤ aᵢ ≤ 5000)，代表每日銷售額。

輸出格式

對每組測試資料，輸出列表 B 中 n − 1 個整數的總和。

解題思路

針對每一天的銷售額，統計前面天數中小於或等於它的銷售次數，並將這些次數加總。使用 vector<int> v 錄歷史銷售額，每輸入一筆新資料時與先前所有資料比較，累加符合條件的次數，最後輸出總和。時間複雜度為 O(n²)。

程式碼

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

int main(){
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> v;
        int ans = 0, a;
        for (int i = 0; i < n; i++) {
            cin >> a;
            for (int j : v) {
                if (j <= a) {
                    ans++;
                }
            }
            v.push_back(a);
        }
        cout << ans << "\n";
    }
}