ZOJ 3819 Average Score：Bob 分數範圍 (枚舉 0~100 驗證雙班平均分增長條件)

問題

Bob 所在班 n 人 (含 Bob)，另一班 m 人。已知除 Bob 外兩班所有人分數。若 Bob 轉去另一班，**兩班平均分都嚴格增長**。求 Bob 分數可能範圍 (0~100 整數)。保證有解。

條件轉化

設 Bob 分數為 x。
原班平均：avg1 = (sum1 + x) / n (sum1 為其餘 n-1 人總分)
另一班平均：avg2 = sum2 / m
轉班後：
原班新平均 avg1' = sum1 / (n-1) (需 > avg1)
另一班新平均 avg2' = (sum2 + x) / (m+1) (需 > avg2)

不等式組

sum1 / (n-1) > (sum1 + x) / n     →  x < sum1 / (n-1)
(sum2 + x) / (m+1) > sum2 / m     →  x > sum2 / m

即：floor(sum2/m) < x < ceil(sum1/(n-1))，且 x ∈ [0,100] 整數。
直接枚舉 0~100 檢查兩不等式即可 (O(101) 極快)。

代碼

#include 
using namespace std;

int main() {
    int T; scanf("%d",&T);
    while (T--) {
        int n,m; scanf("%d%d",&n,&m);
        double sum1=0, sum2=0;
        for (int i=0;i avg1 && avg2p > avg2) {
                lo = min(lo, x);
                hi = max(hi, x);
            }
        }
        printf("%d %d\n", lo, hi);
    }
    return 0;
}

樣例驗證

輸入：
2
4 3
5 5 5
4 4 3
6 5
5 5 5 4 5
3 1 3 2 2 1
輸出：
4 4
2 4
符合條件。