NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #198042 | #3456. 跑步比赛 | baiencheng | 100 | 1216ms | 4480kb | C++ | 1.0kb | 2023-11-19 13:47:29 | 2023-11-19 16:05:28 |
answer
#include<bits/stdc++.h>
#include<ctime>
#define int long long
#define itn int
#define ull unsigned long long
#define ll long long
using namespace std;
struct node{
int v,w;
}a[100005];
int n;
bool check(int num){
priority_queue<int> p1,p2;
for(int i=1;i<=n;i++){
if(num>a[i].v) p1.push(a[i].w);
else p2.push(a[i].v-num+a[i].w);
}
while(1){
if(p1.empty()==1||p2.empty()==1){
return p1.empty();
}
if(p1.top()>p2.top()) return false;
p1.pop();
p2.pop();
}
}
int t;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].v>>a[i].w;
int l=1,r=1000000000,ans=0;
while(l<=r){
int mid=l+((r-l)>>1);
if(check(mid)==1){
l=mid+1;
ans=mid;
} else r=mid-1;
}
cout<<ans<<"\n";
}
return 0;
}
//296+28+128
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1268kb
input:
1 10 266993 706803678 802362985 892644371 953855359 196462821 817301757 409460796 773943961 48876395...
output:
555904242
result:
ok single line: '555904242'
Test #2:
score: 10
Accepted
time: 0ms
memory: 1264kb
input:
1 10 46 15 50 98 93 77 31 43 84 90 6 24 14 37 73 29 43 9 4 8
output:
46
result:
ok single line: '46'
Test #3:
score: 10
Accepted
time: 0ms
memory: 1276kb
input:
20 300 538289667 450937378 534888897 527066716 80798460 335568208 947853348 207336428 510842953 1625...
output:
505659071 550791327 628691185 463559292 127705784 468121697 411937181 435008942 421342654 510493557 ...
result:
ok 20 lines
Test #4:
score: 10
Accepted
time: 0ms
memory: 1276kb
input:
20 83 8 14 31 91 97 72 23 73 68 70 51 78 2 19 10 38 11 16 19 64 97 47 43 65 28 88 63 50 49 23 28 37 ...
output:
44 58 46 64 57 64 43 66 46 52 57 61 46 53 73 39 53 54 42 43
result:
ok 20 lines
Test #5:
score: 10
Accepted
time: 2ms
memory: 1312kb
input:
1 1000 93 758062633 88 981601925 22 28054989 72 269036456 41 161626551 15 521363191 3 244982120 50 2...
output:
20
result:
ok single line: '20'
Test #6:
score: 10
Accepted
time: 4ms
memory: 1312kb
input:
1 1000 223444244 49 154763608 49 914282513 57 594690778 49 46129939 20 592083152 16 459436308 39 650...
output:
534391186
result:
ok single line: '534391186'
Test #7:
score: 10
Accepted
time: 476ms
memory: 2964kb
input:
2 53954 706803678 802362985 892644371 953855359 196462821 817301757 409460796 773943961 488763959 40...
output:
497979099 497530880
result:
ok 2 lines
Test #8:
score: 10
Accepted
time: 144ms
memory: 3196kb
input:
2 34643 15 50 98 93 77 31 43 84 90 6 24 14 37 73 29 43 9 4 8 14 31 91 97 72 23 73 68 70 51 78 2 19 1...
output:
50 50
result:
ok 2 lines
Test #9:
score: 10
Accepted
time: 125ms
memory: 4480kb
input:
1 100000 93 758062633 88 981601925 22 28054989 72 269036456 41 161626551 15 521363191 3 244982120 50...
output:
23
result:
ok single line: '23'
Test #10:
score: 10
Accepted
time: 465ms
memory: 4424kb
input:
1 100000 223444244 49 154763608 49 914282513 57 594690778 49 46129939 20 592083152 16 459436308 39 6...
output:
499790184
result:
ok single line: '499790184'
Extra Test:
score: 0
Extra Test Passed
