CFR 215 D. Hot Days ( Greedy )

Problem - 215D - Codeforces

題意：
有 N 個地點要依序拜訪。每個地點都要叫至少一台車，一台車的花費為 cost。車的溫度為 t，學生能忍受的溫度為 T。一個車內如果有 x 個學生，那麼該車的溫度為 t + x。對於一個車，如果車的溫度大於 T，在車裡面的所有學生都要分別賠償 x。求最小總花費。

資料規模：
The first input line contains two integers n and m (1 ≤ n ≤ 1e5; 1 ≤ m ≤ 1e6) — the number of regions on the way and the number of schoolchildren in the group, correspondingly. Next n lines contain four integers each: the i-th line contains ti, Ti, xi and costi (1 ≤ ti, Ti, xi, costi ≤ 1e6). The numbers in the lines are separated by single spaces.

解法：
先把好處理的情形移除：
t ≥ T：反正怎麼分配都一定要賠償所有人，大家擠一台車一定比較好
t + M ≤ T：反正怎麼分配都不需要賠償任何人，大家擠一台車一定比較好
否則的話，就需要考慮有至少兩台車的情況。
但如果相對於所有人擠一台車，把 T - t 個人搬出去坐一台新的車比較好，那麼再從原本的車把 T - t 個人搬出去一定更好 ...，因此真正需要考慮的情形還是只有兩種：全部坐一起賠償，或者用最少的車分配，使得不必賠償任何人。

時間 / 空間複雜度：
O( N )

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

#define int long long

int N, M;

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  int ans = 0;
  for( int i = 0; i < N; ++i ){
    int t, T, x, cost; cin >> t >> T >> x >> cost;
    if( t + M <= T ) ans += cost;
    else if( t >= T ) ans += cost + x * M;
    else ans += min( cost + x * M, cost * ( ( M + T - t - 1 ) / ( T - t ) ) );
  }
  cout << ans << endl;
  return 0;
}