1 条题解

  • 0
    @ 2023-3-13 11:51:14

    C++ :

    #include<bits/stdc++.h>
    using namespace std;
    struct Node{
        int z,b;double t,p;
        bool operator <(const Node a)const{
            if(t==a.t)return p<a.p;
            return t<a.t;
        }    
    };
    struct Nd{int b;double a;};
    int n,b,x,c,Z[10010],B[10010];double a;
    vector<Nd>V[110];
    priority_queue<Node>Q;
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&a,&b);
            V[b].push_back((Nd){i,a});
        }
        for(int i=2;i<=100;i++)for(int j=0;j<V[i].size();j++)
        for(int u=i-1;u>=1;u--)for(int v=V[u].size()-1;v>=0;v--)
            if(V[i][j].a<V[u][v].a){
                x++;
                double t=(V[u][v].a-V[i][j].a)/(i-u),p=V[u][v].a+u*t;
                Q.push((Node){V[i][j].b,V[u][v].b,t,p});
                if(Q.size()>10000)Q.pop();
            }
        while(!Q.empty()){c++;Z[c]=Q.top().z;B[c]=Q.top().b;Q.pop();}
        printf("%d\n",x);
        for(int i=c;i>=1;i--)printf("%d %d\n",Z[i],B[i]);
        return 0;
    }
    /*
    7
    3 8
    4 2
    5 1
    6 7
    7 8
    9 7
    10 8
    */
    
    
    • 1

    信息

    ID
    1813
    时间
    1000ms
    内存
    16MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者