* 1、题目描述 * * 有股神吗？ 有，小赛就是！ * 经过严密的计算，小赛买了一支股票，他知道从他买股票的那天开始，股票会有以下变化：第一天不变，以后涨一天，跌一天，涨两天，跌一天，涨三天，跌一天…依此类推。 * 为方便计算，假设每次涨和跌皆为1，股票初始单价也为1，请计算买股票的第n天每股股票值多少钱？
import java.util.Scanner; /** * * @author MaiBenBen */ public class GuShen { /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here // int date; //方法一 // Scanner sc = new Scanner(System.in); // date = sc.nextInt(); // int price, priceDownNum; // priceDownNum = (int) (Math.sqrt(2 * date + 0.25) - 1.5); // price = date - 2 * priceDownNum; // System.out.println(price); Scanner sc = new Scanner(System.in); //方法二，当天数为3，6，9，10...时股票数减2即可，其他依次增加。 int m = sc.nextInt(); int res=0;int k=2;int p=3; for(int i=1;i<=m;i++){ if(i==p){ res-=2;k++;p+=k; } res+=1; } System.out.println(res); } }*2、 题目描述 ：某餐馆有n张桌子，每张桌子有一个参数：a 可容纳的最大人数； 有m批客人，每批客人有两个参数:b人数，c预计消费金额。 * 在不允许拼桌的情况下，请实现一个算法选择其中一部分客人，使得总预计消费金额最大 输入描述: 输入包括m+2行。 第一行两个整数n(1 <= n * <= 50000),m(1 <= m <= 50000) 第二行为n个参数a,即每个桌子可容纳的最大人数,以空格分隔,范围均在32位int范围内。 * 接下来m行，每行两个参数b,c。分别表示第i批客人的人数和预计消费金额,以空格分隔,范围均在32位int范围内。 输出描述: * 输出一个整数,表示最大的总预计消费金额 * 示例1 输入 * * 3 5 * 2 4 2 * 1 3 * 3 5 * 3 7 * 5 9 * 1 10 输出 *
import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; /** * * @author MaiBenBen */ public class BigRest implements Comparable<BigRest> { /* * * 20 @param args the command line arguments * * * 思路：贪心算法，将桌子递增排序，然后将人数小于最大桌能容量的客人压入优先队列，其中优先队列 * 降序排列，依次从队列中最大钱数循环寻找桌子数组中最小能容纳的桌子，直到桌子坐满或客人安排完结束。 */ private int num; private int money; public BigRest(int num, int money) { this.num = num; this.money = money; } public static void main(String[] args) { // TODO code application logic here Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = in.nextInt(); } Arrays.sort(a); //升序 // for(int i=0;i<n;i++){ // System.out.println(a[i]); // } PriorityQueue<BigRest> pq = new PriorityQueue<>(); for (int j = 0; j < m; j++) { int d = in.nextInt(); int b = in.nextInt(); if (d <= a[n - 1]) { pq.add(new BigRest(d, b)); } } int sum = 0; boolean[] bs = new boolean[n]; int count = 0; while (!pq.isEmpty()) { BigRest bigRest = pq.poll(); for (int i = 0; i < n; i++) { if (bigRest.num <= a[i] && !bs[i]) { sum += bigRest.money; bs[i] = true; count++; break; } } if (count == n) { break; } } System.out.println(sum); // TreeMap<Integer,Integer> map=new TreeMap<Integer, Integer>(); //键值对中键值需要唯一的 // for(int j=0;j<m;j++){ // int q=in.nextInt(); // int b=in.nextInt(); // map.put(q, b); // } // for(int i=0;i<m;i++){ // System.out.println(map.pollLastEntry()); // } } @Override public int compareTo(BigRest t) { //构造比较器，大到小排列 if (t.money > this.money) { return 1; } else if (t.money < this.money) { return -1; } else { return 0; } } }