A和B是好友，他们经常在空闲时间聊天，A的空闲时间为[a1 ,b1 ],[a2 ,b2 ]..[ap ,bp ]。B的空闲时间是[c1 +t,d1 +t]..[cq +t,dq +t],这里t为B的起床时间。这些时间包括了边界点。B的起床时间为[l,r]的一个时刻。若一个起床时间能使两人在任一时刻聊天，那么这个时间就是合适的，问有多少个合适的起床时间？
[编程题]聊天
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String[] str = sc.nextLine().split(" ");
int p = Integer.parseInt(str[0]);
int q = Integer.parseInt(str[1]);
int l = Integer.parseInt(str[2]);
int r = Integer.parseInt(str[3]);
int[][] a = new int[p][2];
int[][] b = new int[q][2];
for(int i=0;i<p;i++){
String[] str1 = sc.nextLine().split(" ");
a[i][0] = Integer.parseInt(str1[0]);
a[i][1] = Integer.parseInt(str1[1]);
}
for(int i=0;i<q;i++){
String[] str2 = sc.nextLine().split(" ");
b[i][0] = Integer.parseInt(str2[0]);
b[i][1] = Integer.parseInt(str2[1]);
}
HashSet<Integer> a_set = new
HashSet<Integer>();
for(int i=0;i<p;i++){
for(int j=a[i][0];j<=a[i][1];j++){
a_set.add(j);
}
}
int count=0;
for(int k=l;k<=r;k++){
HashSet<Integer> b_set = new
HashSet<Integer>();
HashSet<Integer> both_set = new
HashSet<Integer>();
for(int i=0;i<q;i++){
for(int j=b[i][0];j<=b[i][1];j++){
b_set.add(j+k);
}
}
both_set.addAll(a_set);
both_set.addAll(b_set);
if(a_set.size()+b_set.size()!=both_set.size()){
count++;
}
}
System.out.println(count);
}
}
}
可能我用的方法比较特殊吧。。。构建set 然后判断集合大小来判断是否重叠。
发表于 2017-03-12 11:14:37
回复(0)
/*
*滑动窗口，动态规划，最大两层循环
*/
//2017-3-2 19:00start
//有重叠即可，出题人描述有问题
//a用一个一维数组表示，符合a的时间段标1.如a有两个时间段15~17,23~26，则a[15]=a[16]=a[17]=1,...其余为0
//b同理，有时间为1，无为0
//a和b加起来，为2则重合
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
int p=sc.nextInt();
int q=sc.nextInt();
int le=sc.nextInt();
int r=sc.nextInt();
sc.nextLine();
//接受p行作为A,先扫描出一个最大的数
int aMax = Integer.MIN_VALUE;
int[][] aData=new int[p][2];
for(int i=0;i<p;i++){
String[] s=sc.nextLine().split(" ");
aMax=Math.max(aMax,Integer.parseInt(s[1]));
aData[i][0]=Integer.parseInt(s[0]);
aData[i][1]=Integer.parseInt(s[1]);
}
int[] a = new int[aMax+1]; //比如最大60，a[60],即有长度61
for(int i=0;i<p;i++){
for(int j=aData[i][0];j<=aData[i][1];j++){
a[j]=1; //a的时间段为1
}
}
int[][] bData=new int[q][2];
for(int i=0;i<q;i++){
String[] s=sc.nextLine().split(" ");
bData[i][0]=Integer.parseInt(s[0]);
bData[i][1]=Integer.parseInt(s[1]);
}
int[] b = new int[aMax+1]; //比如最大60，a[60],即有长度61
for(int i=0;i<q;i++){
for(int j=bData[i][0];j<=Math.min(aMax,bData[i][1]);j++){
b[j]=1; //a的时间段为1
}
}
//以上的这些过程只是在无聊的存储数据罢了，a[]中存了0和1，b[]中存了0和1
int count=0;
//这个双层循环才是核心，a不动，b滑动窗口
while(le<=r&&le<a.length){
for(int i=0;i+le<a.length;i++){
if(b[i]+a[i+le]==2){
count++;
break;
}
}
le++;
}
System.out.println(count);
}
}
}
发表于 2017-03-03 12:20:57
回复(1)
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in) ;
while (input.hasNext()){
int p = input.nextInt() ;
int q = input.nextInt() ;
int l = input.nextInt() ;
int r = input.nextInt() ;
int[][] a= new int[p][] ;
int[][] b= new int[q][] ;
for (int i = 0; i < p; i++) {
a[i] = new int[2] ;
a[i][0] = input.nextInt();
a[i][1] = input.nextInt() ;
}
for (int i = 0; i < q; i++) {
b[i] = new int[2] ;
b[i][0] = input.nextInt();
b[i][1] = input.nextInt() ;
}
int res = fun(p, a, q, b, l, r);
System.out.println(res);
}
}
//实现方法
public static int fun(int p, int[][] a, int q, int[][] b, int l, int r) {
Set<Integer> hash = new HashSet<>(); //存放可行的t
for (int i = 0; i < q; i++) {
//对于b每个时间段
for (int j = 0; j < p; j++) {
//配合a的每个时间段，有哪些t时间符合：相当于向右平移t距离使得和a有重合
int st = Math.max(0, a[j][0] - b[i][1]);//a的左端点-b的右端点，小于0则取0
int ed = Math.max(0, a[j][1] - b[i][0]);//a的右端点-b的左端点，小于0则取0
for (int k = Math.max(l, st); k <= Math.min(r, ed); k++) { //平移t不能超出[l,r]区间
hash.add(k);
}
}
}
return hash.size() ;
}
}
编辑于 2016-08-27 15:33:00
回复(0)
import java.util.*;
public class Main {
public static boolean isProper(int[][] A, int[][] B, int d) {
for (int i = 0; i < A.length; ++i) {
int a1 = A[i][0];
int a2 = A[i][1];
for (int j = 0; j < B.length; ++j) {
int b1 = B[j][0];
int b2 = B[j][1];
if (b1 <= a2 && b2 >= a1)
return true;
}
}
return false;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int p = scanner.nextInt();
int q = scanner.nextInt();
int l = scanner.nextInt();
int r = scanner.nextInt();
int[][] A = new int[p][2];
int[][] B = new int[q][2];
for (int i = 0; i < p; ++i) {
A[i][0] = scanner.nextInt();
A[i][1] = scanner.nextInt();
}
for (int j = 0; j < q; ++j) {
B[j][0] = scanner.nextInt();
B[j][1] = scanner.nextInt();
}
int count = 0;
for (int i = l; i <= r; ++i) {
if (isProper(A, B, i)) {
++count;
}
}
System.out.println(count);
}
}
}
土办法，暴力解题。这里只要有一个区间满足就可以对计数做加1。
发表于 2016-08-26 14:21:19
回复(7)
public class freechat {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int p=in.nextInt();
int q=in.nextInt();
int l=in.nextInt();
int r=in.nextInt();
int[][] a = new int[p][2];
int[][] b = new int[q][2];
for(int i=0;i<p;i++){
for(int j=0;j<2;j++){
a[i][j]=in.nextInt();
}
}
for(int i=0;i<q;i++){
for(int j=0;j<2;j++){
b[i][j]=in.nextInt();
}
}
int n=new freechat().getcount(p, q, l, r, a, b);
System.out.println(n);
}
}
public int getcount(int p,int q,int l,int r,int[][] a,int[][] b){
int num=0;
for(int m=l;m<=r;m++){
mtiao:for(int i=0;i<q;i++){
for(int j=0;j<p;j++){
if((b[i][0]+m<=a[j][1])&&(b[i][1]+m>=a[j][0])){
num++;
break mtiao;
}
}
}
}
return num;
}
}
编辑于 2016-08-24 11:35:36
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-04 15:46:13
-
2022-08-31 15:41:24 -
2022-08-26 22:32:45
-
2022-08-26 06:53:18 -
2022-08-25 14:42:07
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
