沧州什么地方可以学建网站,wordpress piklist,腾讯云服务器费用,短剧小程序开发【蔚来汽车】蔚来20220713第三题-旅游规划 牛牛对 n 个城市旅游情况进行了规划#xff0c;已知每个城市有两种属性 x 和 y #xff0c;其中 x 表示去第 i 号城市的花费#xff0c;y 表示在第 i 号城市游玩后会得到的开心值。 现在牛牛希望从中挑选出一些城市去游玩…【蔚来汽车】蔚来20220713第三题-旅游规划 牛牛对 n 个城市旅游情况进行了规划已知每个城市有两种属性 x 和 y 其中 x 表示去第 i 号城市的花费y 表示在第 i 号城市游玩后会得到的开心值。 现在牛牛希望从中挑选出一些城市去游玩但挑选出的城市必须满足任意两个城市之间花费差值的绝对值小于 k 请你帮他计算出在满足上述条件下能得到最大的开心值是多少
输入描述 第一横输入两个整数 n 和 k 接下来 n 行每行输入两个整数 x 和 y 分别表示每个城市的两种属性 1 n 100000 1 k 1000000000 0 x,y 1000000000
输出描述 输出一个整数表示答案
示例输入
5 3
1 3
2 1
5 2
3 1
4 3示例输出
6题解
模拟先按 x 的大小先排好序再求最大价值的连续区间
public class Solution {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int k in.nextInt();int[][] cities new int[n][2];for (int i 0; i n; i) {cities[i][0] in.nextInt();cities[i][1] in.nextInt();}Arrays.sort(cities, (a, b) - a[0] - b[0]);int maxHappy 0;int curHappy 0;/* //滑动窗口解法for(int i0,j0; in; i){//当前的Happy值curHappy cities[i][1];while (ji cities[i][0]-cities[j][0] k){curHappy - cities[j][1];j;}maxHappy Math.max(maxHappy,curHappy);}*/for (int i 0; i n; i) {int j i 1;//当前的Happy值curHappy cities[i][1];while (j n cities[j][0] - cities[i][0] k) {curHappy cities[j][1];j;}maxHappy Math.max(maxHappy, curHappy);}System.out.println(maxHappy);}
}
