題目連結:hihoCoder 1249 Xiongnu’s Land
代碼
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = ;
int N, R, L[maxn], T[maxn], W[maxn], H[maxn];
ll S;
ll get(int x) {
ll ret = ;
for (int i = ; i < N; i++)
ret += L * H[i] * max(min(W[i], x - L[i]), );
return ret;
}
int solve () {
int l = , r = R + ;
while (l < r) {
int mid = (l + r) >> ;
ll tmp = get(mid);
if (tmp >= S - tmp) r = mid;
else l = mid + ;
}
ll ans = get(r);
l = , r = R + ;
while (l < r) {
int mid = (l + r) >> ;
if (get(mid) > ans) r = mid;
else l = mid + ;
}
return l - ;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
S = ;
scanf("%d%d", &R, &N);
for (int i = ; i < N; i++) {
scanf("%d%d%d%d", &L[i], &T[i], &W[i], &H[i]);
S += L * W[i] * H[i];
}
printf("%d\n", solve());
}
return ;
}