贪心

[Ir1d]

https://oi-wiki.cf/basic/greedy/

[bool2002]

太厉害了

[wuxianao]

为什么国王游戏还要高精度啊 : (

[dengjiaqiang01]

因为a,b<=10^4，n个全部乘起来很大很大

[ZhaoYu2015]

意思是工作不能重复做啊，我看代码纠结了半天，感觉题目不是很明确。

[coderoadline]

通透

[wujunye1212]

丝滑

[zhangjialin996]

国王游戏：java代码

import java.util.*;

public class KingGame {
  public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    int num = in.nextInt();
    int[][] list = new int[num+1][];
    for(int i = 0; i <= num; i++){
      int[] temp = new int[2];
      temp[0] = in.nextInt();
      temp[1] = in.nextInt();
      list[i] = temp;
    }

    // king must be the first one
    Arrays.sort(list, 1, list.length, (o1, o2)->{
      return Math.max(o2[1], o1[0]*o1[1])-Math.max(o1[1], o2[0]*o2[1]);
    });

    int sum = 1;
    for(int i = 0;i < num;i++){
      sum *= list[i][0];
    }
    System.out.println(sum/list[num][1]);;
  }
}

[zhangjialin996]

上面代码有问题，因为精度问题，只能说有点离谱的。。。

import java.math.BigInteger;
import java.util.*;

public class KingGame {
  public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    int num = in.nextInt();
    long[][] list = new long[num+1][];
    for(int i = 0; i <= num; i++){
      long[] temp = new long[2];
      temp[0] = in.nextLong();
      temp[1] = in.nextLong();
      list[i] = temp;
    }

    // king must be the first one
    Arrays.sort(list, 1, list.length, (o1, o2)->{
      return Math.max(o2[1], o1[0]*o1[1])-Math.max(o1[1], o2[0]*o2[1])>0?1:-1;
    });

    BigInteger sum = new BigInteger("1");
    for(int i = 0;i < num;i++){
      sum = sum.multiply(BigInteger.valueOf(list[i][0]));
      // System.out.println(BigInteger.valueOf(list[i][0]));
      // System.out.println(sum);
      // System.out.println(list[i][0]);
      // System.out.println(list[i][1]);
    }
    // System.out.println(sum);
    // System.out.println(list[num][0]);
    // System.out.println(list[num][1]);
    System.out.println(sum.divide(BigInteger.valueOf(list[num][1])));;
  }
}

[zhangjialin996]

工作调度：java使用PriorityQueue实现有序队列维护，它的底层是一个最小堆实现，每次队列满的时候要插入新元素，就和队列头比较，比队列头大说明需要进行“后悔”，否则不作这个工作。

import java.util.*;

public class P2949 {
  public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    int num = in.nextInt();
    int[][] jobs = new int[num][2];
    for(int i = 0; i < num; i++){
      int[] temp = new int[2];
      temp[0] = in.nextInt();
      temp[1] = in.nextInt();
      jobs[i] = temp;
    }

    Arrays.sort(jobs, (o1, o2)->{
      return o1[0] - o2[0];
    });

    int timer = 0;
    long profit = 0;
    PriorityQueue<int[]> queue = new PriorityQueue<>((o1,o2)->{
      return o1[1]-o2[1];
    });
    for(int i = 0; i < num; i++){
      timer = jobs[i][0];
      if(queue.size() < timer){
        queue.add(jobs[i]);
        profit += jobs[i][1];
      }else if(jobs[i][1] > queue.peek()[1]){
        int[] temp = queue.poll();
        profit -= temp[1];
        queue.add(jobs[i]);
        profit += jobs[i][1];
      }
    }

    System.out.println(profit);

  }
}

[zhangjialin996]

修理牛棚：
思路：在第一个棚位和最后一个棚位之间，减去最大的几个间隔即可【注意：题目没告诉你输入的牛所在的棚位索引是有序的！】

import java.util.*;

public class P1209 {
  public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    int WoodNum = in.nextInt();
    int houseNum = in.nextInt();
    int cowNum = in.nextInt();
    int[] cow = new int[cowNum];
    Integer[] span = new Integer[cowNum - 1];

    for(int i = 0; i < cowNum; i++){
      cow[i] = in.nextInt();
    }
    Arrays.sort(cow);
    in.close();

    for(int i = 1; i < cowNum; i++){
      span[i-1] = cow[i] - cow[i-1] - 1;
    }
    Arrays.sort(span, (o1, o2)->o2-o1);

    int res = cow[cow.length -1] - cow[0] + 1;
    for(int i = 0; i < Math.min(WoodNum - 1, span.length); i++){
      res -= span[i];
    }
    System.out.println(res);
  }  
}

[zhangjialin996]

我是准备面试的，皇后游戏我认为太难了orz，不写了

[Heshu525]

反悔贪心怎么只写了这么一点

[xiao-ming-hub]

是啊感觉好少

[HuangDuoYan]

为什么没有拟阵？