QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#135455 | #6693. Fast and Fat | yj | WA | 1ms | 3456kb | C++14 | 1.2kb | 2023-08-05 15:35:31 | 2023-08-05 15:35:32 |
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 = (maxv + minv) >> 1;
if (check(midv))
minv = midv + 1;
else
maxv = midv;
}
cout << maxv << endl;
}
int main() {
int t;
cin >> t;
while (t--)
solve();
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3456kb
input:
2 5 10 5 1 102 10 100 7 4 9 50 2 1 100 10 1
output:
9 2
result:
wrong answer 1st numbers differ - expected: '8', found: '9'