算法训练 Beaver's Calculator

本是古典何须时尚 2022-03-08 03:17 129阅读 0赞

问题描述

从万能词典来的聪明的海狸已经使我们惊讶了一次。他开发了一种新的计算器，他将此命名为"Beaver's Calculator 1.0"。它非常特别，并且被计划使用在各种各样的科学问题中。  
　　为了测试它，聪明的海狸邀请了n位科学家，编号从1到n。第i位科学家给这个计算器带来了 *k**i*个计算题。第i个科学家带来的问题编号1到n，并且它们必须按照编号一个一个计算，因为对于每个问题的计算都必须依赖前一个问题的计算结果。  
　　每个教授的每个问题都用一个数 *a**i*, *j*  来描述，i（1≤i≤n）是科学家的编号，j（1≤j≤ *k**i* ）是问题的编号， *a**i*, *j*  表示解决这个问题所需资源单位的数量。  
　　这个计算器非常不凡。它一个接一个的解决问题。在一个问题解决后，并且在下一个问题被计算前，计算器分配或解放资源。  
　　计算器中最昂贵的操作是解放资源，解放远远慢于分配。所以对计算器而言，每一个接下来的问题所需的资源不少于前一个，是非常重要的。  
　　给你关于这些科学家所给问题的相关信息。你需要给这些问题安排一个顺序，使得“坏对”尽可能少。  
　　所谓“坏对”，就是相邻两个问题中，后一个问题需求的资源比前一个问题少。别忘了，对于同一个科学家给出的问题，计算它们的相对顺序必须是固定的。

输入格式

第一行包含一个整数n，表示科学家的人数。接下来n行每行有5个整数，*k**i*, *a**i*, 1, *x**i*, *y**i*, *m**i* (0 ≤ *a**i*, 1 < *m**i* ≤ 109, 1 ≤ *x**i*, *y**i* ≤ 109) ，分别表示第i个科学家的问题个数，第1个问题所需资源单位数，以及3个用来计算 *a**i*, *j* 的参量。*a**i*, *j* = (*a**i*, *j* - 1 \* *x**i* + *y**i*)*mod* *m**i。*

输出格式

第一行输出一个整数，表示最优顺序下最少的“坏对”个数。  
　　如果问题的总个数不超过200000,接下来输出 ![a16730dcbb2402871e20647c8aba55beada5c1b6.png][] 行，表示解决问题的最优顺序。每一行两个用空格隔开的整数，表示这个问题所需的资源单位数和提供这个问题的科学家的编号。

样例输入

2  
2 1 1 1 10  
2 3 1 1 10

样例输出

0  
1 1  
2 1  
3 2  
4 2

数据规模和约定

20%的数据 *n* = 2, 1 ≤ *k**i* ≤ 2000；  
　　另外30%的数据 *n* = 2, 1 ≤ *k**i* ≤ 200000；  
　　剩下50%的数据 1 ≤ *n* ≤ 5000, 1 ≤ *k**i* ≤ 5000。

每个科学家k个问题的相对顺序不能改变,所以对于每个科学家来说他们问题本身的顺序就有可能存在坏对,、对于同一个科学家的问题,只要求相对顺序不变就好,因此他们可以拆开插到别的科学家的问题之间。先分别记录每个科学家问题顺序出现的坏对的值，然后求得最大值即为最少的坏对的个数，每当出现坏对时，我们就对其进行分层，然后分层排序，保证了相对顺序不会改变。

#include<bits/stdc++.h>
    using namespace std;
    
    struct pro{
        int t;
        int value;
        int sci;
    }p[200001];
    int cmp(pro x,pro y){
        if(x.t==y.t){
            return x.value<y.value||(x.value==y.value&&x.sci<y.sci);
        }
        return x.t<y.t;
    }
    int main()
    {
        long long int n,k,a,b,x,y,m;
        int cnt=0,num=-1;
        cin>>n;
        for(int i=1;i<=n;i++){
            int t=0;
            cin>>k>>a>>x>>y>>m;
            for(int j=1;j<=k;j++){
                if(cnt<=2e5)p[cnt++]=(pro){t,a,i};
                b=(x*a+y)%m;
                if(b<a&&j!=k)t++;
                a=b;
            }
            num=max(num,t);
        }
        cout<<num<<endl;
        if(cnt<=2e5){
            sort(p,p+cnt,cmp);
            for(int i=0;i<cnt;i++){
                cout<<p[i].value<<" "<<p[i].sci<<endl;
            }
        }
        return 0;
    }

[a16730dcbb2402871e20647c8aba55beada5c1b6.png]: /images/20220308/f3f9c4cdb3a64912b60c206176a79785.png