贪心-C - Canoe

落日映苍穹つ 2023-07-12 08:45 88阅读 0赞

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

# 思考： #

想想放谁上船，如果全是小体重的上船，看似会最小船数，但是，对于体重大的人来是，他们一个人就占了大半条船，想让更重的人来坐已经不行的了，但是这些空的小地方留给小的，最好是刚刚能填满的人来坐最好了

import java.util.*;
    public class 贪心_1 {
        
        static int s;
        static int w,n,gg,i,j,jojo,dio,kazi;
        public static void main(String[] args) {
        
            Scanner scanner=new Scanner(System.in);
            int t=scanner.nextInt();
            while (t>0){
        
                t--;
                if (t<0) break;
                int w=scanner.nextInt();
                int n=scanner.nextInt();
                int a[]=new int[n];
                for (int o=0;o<n;o++){
        
                    a[o]=scanner.nextInt();
                }
                Arrays.sort(a);
                kazi=0;
                gg=0; i=0; j=n-1;
                while(gg<n){
        
                    if (i==j){
        
                        kazi++;
                        break;
                    }
                    jojo=a[i];
                    dio=a[j];
                    if (jojo+dio<=w){
        //最大配最小
                        kazi++;
                        gg+=2;
                        i++;
                        j--;
                    }
                    else {
        //如果最小和最大超过了w，就只是让最大的去做
                        kazi++;
                        gg++;
                        j--;
                    }
                }
                System.out.println(kazi);
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/202003072009113.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200307200916537.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng==,size_16,color_FFFFFF,t_70