疑问

P1168 中位数

Mr_ll @ 2021-10-13 19:39:21

已AC(代码)(码风较丑,勿怪)

#include<iostream>
#include<cmath>
#include<cstdio>
#include<queue>
using namespace std;
const int N=1e5+5;
int n;
priority_queue<long long> da,xiao;
long long a[N],mid;
int main(){
    scanf("%d",&n);
    scanf("%lld",&a[1]);
    mid=a[1];da.push(a[1]);
    printf("%lld\n",a[1]);
    for(int i=2;i<=n;i++){
        scanf("%lld",&a[i]);
        if(a[i]>mid) xiao.push(-a[i]);
        else da.push(a[i]);
        while(da.size()>xiao.size()){xiao.push(-da.top());da.pop();}
        while(xiao.size()>da.size()){da.push(-xiao.top());xiao.pop();}
        if(da.size()>xiao.size()) mid=da.top();
        else mid=-xiao.top();
        if(i%2==1)printf("%lld\n",mid);
    }
    return 0;
}

while里改成>0就不运行了

#include<iostream>
#include<cmath>
#include<cstdio>
#include<queue>
using namespace std;
const int N=1e5+5;
int n;
priority_queue<long long> da,xiao;
long long a[N],mid;
int main(){
    scanf("%d",&n);
    scanf("%lld",&a[1]);
    mid=a[1];da.push(a[1]);
    printf("%lld\n",a[1]);
    for(int i=2;i<=n;i++){
        scanf("%lld",&a[i]);
        if(a[i]>mid) xiao.push(-a[i]);
        else da.push(a[i]);
        while(da.size()-xiao.size()>0){xiao.push(-da.top());da.pop();}
        while(xiao.size()-da.size()>0){da.push(-xiao.top());xiao.pop();}
        if(da.size()>xiao.size()) mid=da.top();
        else mid=-xiao.top();
        if(i%2==1)printf("%lld\n",mid);
    }
    return 0;
}

by Dangerou @ 2021-10-14 15:17:31

@Mr_ll 虽然我不知道怎么错的,但是我知道 新版 C++ while 循环里面要加括号,不然他会警告


by hahaha1215 @ 2022-03-02 20:58:27

队列的size()函数返回值是unsigned\ int类型,而unsigned\ int 类型的范围是[0,2^{32}-1],两个unsigned\ int类型相减自然还是unsigned\ int类型,也就是说不会出现负数!!!所以拿两个队列的size值相减的时候要转化成int类型!

只要改成while((int)(da.size()-xiao.size())>0)就好了!


|