Java实现洛谷P1250 种树（暴力）

Yasmin ·

更新时间:2024-09-21

· 646 次阅读

P1250 种树

在这里插入图片描述

输入输出样例
输入  
9
4
1 4 2
4 6 2
8 9 2
3 5 2
输出 
5

PS：
我种最少的树，意味着我的树要最多的被利用，意味着，我的树要尽可能的靠中间种，
也就是我把右区间从小到大排序，如果区间树不够，就从右往左种

 
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int maxlen = sc.nextInt();
		int n = sc.nextInt();
		Node[] nodes = new Node[n];
		for (int i = 0; i < nodes.length; i++) { 
			nodes[i] = new Node(sc.nextInt(), sc.nextInt(), sc.nextInt());
		}
		sc.close();
		//排序是按照右面从小到大， 
		//这里不断利用中间的点，
		//相反，我如果按照右面从大到小， 我就是不断取最两边的点
		Arrays.sort(nodes);
		boolean[] bool = new boolean[maxlen + 1];
		int count = 0;
		for (int i = 0; i < nodes.length; i++) {
			int nums = 0;
			//看当前区间有多少种树的
			for (int j = nodes[i].left; j <= nodes[i].right; j++) {
				if (bool[j]) {
					nums++;
				}
			}
			//如果不够的话，在往中间加树，加到符合条件
			int j = nodes[i].right;
			while (nums < nodes[i].value) { 
				if (!bool[j]) {
					//加树的过程记录加的数量
					count++;
					nums++;
					bool[j] = true; 
				}
				j--;
			}
		}
		System.out.println(count);
	}
}
class Node implements Comparable {
	int left;
	int right;
	int value;
	public Node(int left, int right, int value) {
		this.left = left;
		this.right = right;
		this.value = value;
	}
	@Override
	public int compareTo(Node o) {
		return this.right - o.right;
	}
}

作者：南墙

p1 JAVA p12

1024 个赞