P1324 矩形分割

比眉伴天荒 2023-07-15 11:22 16阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]

# java唉，过不了 #

import java.util.Arrays;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.Scanner;
    
    public class 二分法2 {
        
        static int max=2100;
    
        boolean cmp(int aa,int bb){
        
            return aa>bb;
        }
        public static void main(String[] args) {
        
    
            Scanner scanner=new Scanner(System.in);
            int n,m;
            n=scanner.nextInt();
            m=scanner.nextInt();
            int max=Math.max(n,m);
    //        Integer a[]=new Integer[max];
    //        Integer b[]=new Integer[max];
            int a[]=new int[m+n];
            int b[]=new int[m+n];
            for(int i=0;i<n-1;i++) {
        
                a[i]=scanner.nextInt();
            }
            for(int i=0;i<m-1;i++) {
        
                b[i]=scanner.nextInt();
            }
    //        Arrays.sort(a,1,n,Collections.reverseOrder());
    //        Arrays.sort(b,1,m,Collections.reverseOrder());
            Arrays.sort(a,0,a.length-1);
            Arrays.sort(b,0,b.length-1);
            int s1=1;
            int s=1;
            int ans=0;
            int c=m+n-2;
            int d=n+m-2;
            for (int i =m+n-2; i >=0; i--) {
        
                if(a[c]>b[d]) {
        
                    ans+=s*a[c--];//选择大的，这里s2表示块数，s1指针后移一位
                    s=s*2;
                }
                else {
        
                    ans+=s*b[d--];//同理，和上面相反
                    s=s*2;
                }
            }
            System.out.print(ans);
        }
    }

#include<cstdio>
    #include<algorithm>//用到sort
    using namespace std;
    const int MAXN=2020;//毕竟刚刚2020~
    int a[MAXN],b[MAXN];//横线和竖线的代价
    bool cmp(int aa,int bb){
        return aa>bb;}//从大到小
    int main(){
        
        int n,m,s1=1,s2=1;//s1和s2可以是a数组和b数组的指针，也可以是横纵分成的块数
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++) scanf("%d",&a[i]);
        for(int i=1;i<m;i++) scanf("%d",&b[i]);
        sort(a+1,a+n,cmp);sort(b+1,b+m,cmp);//从大到小排序
        long long ans=0;//记录答案，注意long long
        for(int i=2;i<n+m;i++){
        //遍历
            if(a[s1]>b[s2]) ans+=s2*a[s1++];//选择大的，这里s2表示块数，s1指针后移一位
            else ans+=s1*b[s2++];//同理，和上面相反
        }
        printf("%lld",ans);
        return 0;//华丽结束
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]: /images/20230528/d4d4f334c7b94609a52f53ebedee960c.png