突然发现为什么我这个代码AC了
查看原帖
突然发现为什么我这个代码AC了
1278879
wjxalex楼主2024/9/30 22:46

很久以前写的,最近重看的时候突然发现我这个好像有问题,最后我直接把手写的二叉堆按1--n+m的顺序遍历输出了,这样怎么保证每t次是由大到小递减的呀,是我歪打正着试出某个证明了还是数据有点水? 如果是的话建议加强数据

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m,qq,u,v,t,x,k,k1,k2;
int q[8000001]={},len=0;
void push(int x1){
    q[++len]=x1;
    int i=len;
    while(i>1&&q[i/2]<q[i]){
        swap(q[i],q[i/2]);
        i=i/2;
    }
}
void pop(){
    q[1]=q[len--];
    int i=1;
    while(i*2<=len){
        int son=2*i;
        if(son<len&&q[son+1]>q[son]){
            son++;
        }
        if(q[son]>q[i]){
            swap(q[i],q[son]);
            i=son;
        }
        else{
            break;
        }
    }
}
int top(){
    return q[1];
}
int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&qq,&u,&v,&t);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        push(x);
    }
    for(int i=1;i<=m;i++){
        k=top();pop();
        k1=(((long double)k+(long double)qq*(i-1))*(long double)u/(long double)v)/1;
        k2=(k+qq*(i-1))-k1;
        push(k1-qq*i);
        push(k2-qq*i);
        if(i%t==0){
            printf("%d ",k+qq*(i-1));
        }
    }
    printf("\n");
    sort(q+1,q+len+1,greater<int>());
    for(int i=t;i<=n+m;i+=t){
        printf("%d ",q[i]+m*qq);
    }
    cout<<endl;
    return 0;
}
2024/9/30 22:46
加载中...