QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#135454 | #6693. Fast and Fat | yj | WA | 110ms | 3480kb | C++14 | 1.2kb | 2023-08-05 15:31:55 | 2023-08-05 15:31:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
struct dui {
ll v;
ll w;
} a[100005], b[100005]; //a按重量,b按能力
bool cmp1(dui a, dui b) {
return a.w > b.w;
}
bool cmp2(dui a, dui b) {
return (a.v + a.w) > (b.v + b.w);
}
bool check(ll v) {
vector<ll>power;
vector<ll>leizhui;
for (int i = 0; i < n; i++)
if (a[i].v < v)
leizhui.push_back(a[i].w);
for (int i = 0; i < n; i++)
if (b[i].v > v)
power.push_back(b[i].v + b[i].w - v);
if (power.size() < leizhui.size())
return false;
for (int i = 0; i < leizhui.size(); i++)
if (leizhui[i] > power[i])
return false;
return true;
}
void solve() {
cin >> n;
ll maxv = 0;
ll minv = 10000000099;
for (int i = 0; i < n; i++) {
ll x, y;
maxv = max(maxv, x);
minv = min(minv, x);
cin >> x >> y;
a[i] = {x, y};
b[i] = {x, y};
}
sort(a, a + n, cmp1);
sort(b, b + n, cmp2);
ll midv = (maxv + minv) >> 1;
while (minv < maxv) {
midv = (1 + maxv + minv) >> 1;
if (check(midv))
minv = midv;
else
maxv = midv - 1;
}
cout << maxv << endl;
}
int main() {
int t;
cin >> t;
while (t--)
solve();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3480kb
input:
2 5 10 5 1 102 10 100 7 4 9 50 2 1 100 10 1
output:
8 1
result:
ok 2 number(s): "8 1"
Test #2:
score: -100
Wrong Answer
time: 110ms
memory: 3456kb
input:
10000 4 280251502 664541723 375808746 641141991 95134537 898607509 455259328 944978891 2 798417052 547329847 785434740 991778535 6 623628702 857611223 275667427 453747403 292209526 283132767 330752033 988721243 470297536 608192332 477186035 325224271 3 280572174 994054447 306566740 923535026 3781360...
output:
352409014 785434740 470297535 280572174 704877362 960871618 691253608 560579094 56873747 399988835 610497257 576427564 636500913 315900405 370430730 526259135 781258283 631916851 300930080 419999539 431930706 479323438 530080164 391912906 708925498 467782812 457987604 389750718 447390353 696516804 4...
result:
wrong answer 3rd numbers differ - expected: '470297536', found: '470297535'