QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142128#6693. Fast and FatLINTONGTL 1ms19056kbC++141.2kb2023-08-18 15:25:392023-08-18 15:25:41

Judging History

你现在查看的是最新测评结果

  • [2023-08-18 15:25:41]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:19056kb
  • [2023-08-18 15:25:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-'0';
        ch=getchar();
    }
    return s*w;
}
int t,n,ans;
struct tree{
    int v,w;
}tr[1000005];
bool cmp(tree a,tree b){
    if(a.v!=b.v)return a.v<b.v;
    return a.w<b.w;
}

bool check(int x){
    priority_queue<int>q1,q2;
    for(int i=1;i<=n;i++){
        if(tr[i].v>=x)q1.push(tr[i].v+tr[i].w-x);
        else q2.push(tr[i].w);
    }
    if(q1.size()<q2.size())return 0;
    for(int i=1;i<=q2.size();i++){
        int x=q1.top(),y=q2.top();
        q1.pop();q2.pop();
        if(x<y)return 0;
    }
    return 1;
}
signed main(){
    t=read();
    while(t--){
        n=read();
        ans=1;
        memset(tr,0,sizeof(tr));
        for(int i=1;i<=n;i++){
            tr[i].v=read(),tr[i].w=read();
        }
        sort(tr+1,tr+n+1,cmp);
        int l=1,r=1000000000;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid))ans=mid,l=mid+1;
            else r=mid-1;
        }
        cout<<ans<<endl;
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 19056kb

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
Time Limit Exceeded

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:

375808746
785434740
470297536
280572174
704877362
960871619
691253609
560579095
136979645
399988835
610497257
576427565
636500913
315900406
370430730
526259135
781258283
631916852
300930080
419999540
667381564
479323438
530080165
391912906
708925499
467782812
457987604
389750718
447390353
696516804
...

result: