首页 > 顺丰8月20笔试,java代码

顺丰8月20笔试,java代码

仅供参考。
第一题:出租服务器,求最大收益,对客户付出的金钱进行贪心

public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt(),m=in.nextInt();//n服务器个数,m客户个数
        Integer[] a=new Integer[n];
        for (int i = 0; i < n; i++) {
            a[i]=in.nextInt();
        }
        int[][] b=new int[m][2];//第一个表示需要的带宽大小,第二个表示可以付出的金钱
        for (int i = 0; i < m; i++) {
                b[i][0]=in.nextInt();
                b[i][1]=in.nextInt();
        }
        Arrays.sort(b, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) {
                if(o1[1]!=o2[1]) return o2[1]-o1[1];//金钱降序排序
                return o1[0]-o1[0];//带宽大小升序排序
            }
        });
        Arrays.sort(a, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) {
                return o1-o2;//升序排序
            }
        });
        int ans=0,n_temp=n;
        for (int i = 0; i < m; i++) {//对客户进行遍历,贪心最大的金钱
            if(n_temp==0) break;//记录已经出租的服务器数
            int select=-1;
            for (int j = 0; j < n; j++) {//给客户安排带宽刚刚够的服务器,将更大的服务器留给后面的用户
                if(a[j]>=b[i][0]) {
                    select=j;
                    a[j]=-1;//用过的服务器标记为-1
                    break;
                }
            }
            if(select!=-1){
                n_temp--;
                ans+=b[i][1];
            }
        }
        System.out.println(ans);
    }

第二题:赏金猎人,求最大收益,先按结束时间进行升序排序,然后DP
给定n,以下n行,每行3个数 s e mon ,分别表示开始时间 结束时间 赏金,求赏金猎人能得到的最大赏金。

class k{
    public int s;//开始时间
    public int e;//结束时间
    public int mon;//赏金

    public k(int s, int e, int mon) {
        this.s = s;
        this.e = e;
        this.mon = mon;
    }
} 

 public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        k[] a=new k[n];

        for (int i = 0; i < n; i++) {
            int s=in.nextInt();
            int e=in.nextInt();
            int mon=in.nextInt();
            a[i]=new k(s,e,mon);
        }
        Arrays.sort(a, new Comparator<k>() { @Override public int compare(k o1, k o2) {
                return o1.e-o2.e;//按照结束时间升序排序
            }
        });

        int[] dp=new int[n];
        dp[0]=a[0].mon;
        for(int i=1;i<n;i++){
            k temp=a[i];
            int itemp=-1;
            for (int j = i-1; j >=0 ; j--) {
                //找出选择了第i个任务后,前边还能够接受的任务(只要接受的任务的结束时间《第i个任务的开始时间就可以,因为前边已经将区间按照结束时间来升序排序了)
                if(temp.s>=a[j].e){
                    itemp=j;
                    break;
                }
            }
            //dp[i-1]表示不选第i个任务,后边表示选第i个任务
            if(itemp==-1){
                dp[i]=Math.max(dp[i-1],temp.mon);
            }
            else dp[i]=Math.max(dp[i-1],temp.mon+dp[itemp]);
        }
        for (int i = 0; i < n; i++) {
            System.out.print(dp[i]+" ");
        }
        System.out.println();
        System.out.println(dp[n-1]);
    }


全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐