网易 重叠矩形的个数
题目描述
平面内有n个矩形, 第i个矩形的左下角坐标为(x1[i], y1[i]), 右上角坐标为(x2[i], y2[i])。
如果两个或者多个矩形有公共区域则认为它们是相互重叠的(不考虑边界和角落)。
请你计算出平面内重叠矩形数量最多的地方,有多少个矩形相互重叠。
输入描述:
输入包括五行。
第一行包括一个整数n(2 <= n <= 50), 表示矩形的个数。
第二行包括n个整数x1[i](-10^9 <= x1[i] <= 10^9),表示左下角的横坐标。
第三行包括n个整数y1[i](-10^9 <= y1[i] <= 10^9),表示左下角的纵坐标。
第四行包括n个整数x2[i](-10^9 <= x2[i] <= 10^9),表示右上角的横坐标。
第五行包括n个整数y2[i](-10^9 <= y2[i] <= 10^9),表示右上角的纵坐标。
输出描述:
输出一个正整数, 表示最多的地方有多少个矩形相互重叠,如果矩形都不互相重叠,输出1。
2
0 90
0 90
100 200
100 200
2
import java.util.*;
public class Main {
// 统计重叠矩形的个数，转换为左下角在其他矩形中的个数，两个矩形重叠，必然，一个矩形的左下角在另一个矩形中
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] x1 = new int[n];
int[] y1 = new int[n];
int[] x2 = new int[n];
int[] y2 = new int[n];
// 只有nextInt 可以不加nextLine
for(int i=0;i<n;i++){
x1[i] = in.nextInt();
}
for(int i=0;i<n;i++){
y1[i] = in.nextInt();
}
for(int i=0;i<n;i++){
x2[i] = in.nextInt();
}
for(int i=0;i<n;i++){
y2[i] = in.nextInt();
}
int ans = 0;
int res = 0;
for(int x:x1){
for (int y:y1){
for (int i=0;i<n;i++){
if(x >= x1[i] && x < x2[i] && y >= y1[i] && y < y2[i]){
ans++;
}
}
// 统计单个左下角在最多矩形数
if(ans >res){
res = ans;
}
ans = 0;
}
}
System.out.println(res);
}
}
牛牛的闹钟
题目描述
牛牛总是睡过头，所以他定了很多闹钟，只有在闹钟响的时候他才会醒过来并且决定起不起床。从他起床算起他需要X分钟到达教室，上课时间为当天的A时B分，请问他最晚可以什么时间起床
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含一个正整数，表示闹钟的数量N(N<=100)。
接下来的N行每行包含两个整数，表示这个闹钟响起的时间为Hi(0<=A<24)时Mi(0<=B<60)分。
接下来的一行包含一个整数，表示从起床算起他需要X(0<=X<=100)分钟到达教室。
接下来的一行包含两个整数，表示上课时间为A(0<=A<24)时B(0<=B<60)分。
数据保证至少有一个闹钟可以让牛牛及时到达教室。
输出描述:
输出两个整数表示牛牛最晚起床时间。
3
5 0
6 0
7 0
59
6 59
6 0
思路是时间转换为相对时间
import java.util.*;
public class Main {
// 思路把时间全部转换为相对时间，进行比较
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
TreeSet<Integer> set = new TreeSet<>();
for(int i=0;i<n;i++){
int x = in.nextInt();
int y = in.nextInt();
set.add(x * 60 + y);
}
int d = in.nextInt();
int h = in.nextInt();
int m = in.nextInt();
int maxTime = h * 60 + m - d;
Integer time = set.floor(maxTime);
System.out.println(time / 60 + " " + time % 60);
}
}
牛牛的背包问题
题目描述
牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。
牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。
牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。
输入描述:
输入包括两行
第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量。
第二行n个正整数v[i](0 <= v[i] <= 10^9),表示每袋零食的体积。
输出描述:
输出一个正整数, 表示牛牛一共有多少种零食放法。
3 10
1 2 4
8
直接生成子集，暴力求解时间复杂度太大
import java.util.*;
public class Main {
// 思路, 生成子集的形式进行
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long w = in.nextLong();
long[] v = new long[n];
for(int i=0;i<n;i++){
v[i] = in.nextLong();
}
int ans = 1;
int len = 1 << n;
for(int i=1;i<len;i++){
long val = 0;
boolean flag = true;
for(int j = 0;j<n;j++){
if(((i >> j)&1) == 1){
val += v[j];
if(val > w) {
flag = false;
break;
}
}
}
if(flag){
ans++;
}
}
System.out.println(ans);
}
}
使用动归会出现数组越界
package com.bupt.learn;
import java.util.*;
public class Main {
// 思路, 生成子集的形式进行
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long w = in.nextInt();
int[] v = new int[n];
for(int i=0;i<n;i++){
v[i] = in.nextInt();
}
long[][] dp = new long[n+1][(int)w+1];
for(int i=0;i<n+1;i++){
dp[i][0] = 1L;
}
for(int i=0;i<w+1;i++){
dp[0][i] = 1L;
}
for(int i=1;i<n+1;i++){
for (int j=1;j<w+1;j++){
if(j >= v[i-1]){
dp[i][j] = dp[i-1][j-v[i-1]] + dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j];
}
}
}
System.out.println(dp[n][(int)w]);
}
}
使用 dfs 搜索进行搜索，统计
import java.util.*;
public class Main {
public static long result = 1;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
long w = input.nextInt();
long[] v = new long[n];
long sum = 0;
for (int i = 0; i < n; i++) {
v[i] = input.nextInt();
sum = sum + v[i];
}
if (sum <= w) {
System.out.println((int) Math.pow(2, n));
} else {
state(v, 0, w, 0);
System.out.println(result);
}
}
public static void state(long[] v,int index, long w, long current){
if (index == v.length)
return;
if (current + v[index] <= w){
result++;
state(v, index+1,w,current+v[index]);
}
state(v,index+1,w,current);
}
}
俄罗斯方块
题目描述
小易有一个古老的游戏机，上面有着经典的游戏俄罗斯方块。因为它比较古老，所以规则和一般的俄罗斯方块不同。
荧幕上一共有 n 列，每次都会有一个 1 x 1 的方块随机落下，在同一列中，后落下的方块会叠在先前的方块之上，当一整行方块都被占满时，这一行会被消去，并得到1分。
有一天，小易又开了一局游戏，当玩到第 m 个方块落下时他觉得太无聊就关掉了，小易希望你告诉他这局游戏他获得的分数。
输入描述:
第一行两个数 n, m
第二行 m 个数，c1, c2, ... , cm ， ci 表示第 i 个方块落在第几列
其中 1 <= n, m <= 1000, 1 <= ci <= n
3 9
1 1 2 2 2 3 1 2 3
2
import java.util.*;
public class Main {
// 思路, 俄罗斯方块，统计短板
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] line = new int[n+1];
int m = in.nextInt();
for(int i=0;i<m;i++){
int x = in.nextInt();
line[x]++;
}
int min = 1002;
for (int i=1;i<=n;i++){
if(min > line[i]){
min = line[i];
}
}
System.out.println(min);
}
}
瞌睡
题目描述
小易觉得高数课太无聊了，决定睡觉。不过他对课上的一些内容挺感兴趣，所以希望你在老师讲到有趣的部分的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度，并以分数量化，以及他在这堂课上每分钟是否会睡着，你可以叫醒他一次，这会使得他在接下来的k分钟内保持清醒。你需要选择一种方案最大化小易这堂课听到的知识点分值。
输入描述:
第一行 n, k (1 <= n, k <= 105) ，表示这堂课持续多少分钟，以及叫醒小易一次使他能够保持清醒的时间。
第二行 n 个数，a1, a2, ... , an(1 <= ai <= 104) 表示小易对每分钟知识点的感兴趣评分。
第三行 n 个数，t1, t2, ... , tn 表示每分钟小易是否清醒, 1表示清醒。
输出描述:
小易这堂课听到的知识点的最大兴趣值。
6 3
1 3 5 2 5 4
1 1 0 1 0 0
16
使用滑动窗口统计区间的最大值
import java.util.*;
public class Main {
// 思路, 先遍历一遍
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int sumTime = 0;
int[] a = new int[n];
int[] t = new int[n];
for(int i=0;i<n;i++){
a[i] = in.nextInt();
}
for(int i=0;i<n;i++){
t[i] = in.nextInt();
}
int max = 0;
for(int i=0;i<n;i++){
if(t[i] == 1){
sumTime += a[i];
}
}
int left = 0,right = 0;
int sum = 0;
while (right < n){
if(right - left < k){
if(t[right] == 0) {
sum += a[right];
}
right++;
}else {
if(t[left] == 0) {
sum -= a[left];
}
left++;
}
max = Math.max(sum,max);
}
System.out.println(sumTime+max);
}
}
网友评论