牛客多校第二场

g题

1.题目大意:构造长度为n的排列p，使得max{lis(p),lds(p)}最小。

其中lis*(p)为p的最长上升子序列的长度，lds(p)为p的最长下降子序列的长度.

2.分析:我们应构造一个sqrt(n)的序列，此时满足题目要求.

3.代码:

#include <cmath>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        scanf("%d",&n);
        int num=ceil(sqrt(n));
        if(num*num==n){
            for(int i=num;i<=n;i+=num){
                int temp=i;
                for(int j=0;j<num;j++){
                    cout<<temp--;
                    if(!(i==n && j==num-1)) cout<<' ';
                }
            }
            cout<<endl;
        }
        else{
            int last=n%num;
            for(int i=num;i<=n-last;i+=num){
                int temp=i;
                for(int j=0;j<num;j++){
                    cout<<temp--<<" ";
                }
            }
            for(int i=0;i<last;i++){
                cout<<n--<<" ";
            }
            cout<<endl;
        }
    }
     
    return 0;
}

j题

1.题目大意:给定一个数列，求一个新的等差数列，使得两者差的平方之和最小

2.分析:我们组当时是用java的线性回归去做的。后面用c++去提交发现，答案错误，可能是精度导致（？

3.代码:

 
public class Main {
    public static void main(String[] args) {
        Scanner input =new Scanner(System.in);
        int t=input.nextInt();
        for(int i=0;i<t;i++){
            int n= input.nextInt();
            int[] num=new int[n];
            for(int j=0;j<n;j++){
                num[j]= input.nextInt();
            }
            double ave=GetAve(num);
            double b=GetB(num,ave);
            double a=GetA(num,b,ave);
            double sum=GetSum(num,b,a);
            System.out.println(sum);
        }
    }
    public static double GetA(int[] num,double b,double ave){
        return ave-b*(num.length+1)/2.0;
    }
    public static double GetB(int[] num,double ave){
        double n=0;
        double m=0;
        for(int i=1;i<= num.length;i++){
            n+=(i-(num.length+1)/2.0)*(num[i-1]-ave);
            m+=Math.pow(i-(num.length+1)/2.0,2);
        }
        return n/m;
    }
    public static double GetSum(int[] num,double b,double a){
        double sum=0;
        for(int i=1;i<= num.length;i++){
            sum+=Math.pow(b*i+a-num[i-1],2);
        }
        return sum;
    }
    public static double GetAve(int[] num){
        double sum=0;
        for(int i=0;i<num.length;i++){
            sum+=num[i];
        }
        return sum/num.length;
    }
}