A和B是好友，他们经常在空闲时间聊天，A的空闲时间为[a1 ,b1 ],[a2 ,b2 ]..[ap ,bp ]。B的空闲时间是[c1 +t,d1 +t]..[cq +t,dq +t],这里t为B的起床时间。这些时间包括了边界点。B的起床时间为[l,r]的一个时刻。若一个起床时间能使两人在任一时刻聊天，那么这个时间就是合适的，问有多少个合适的起床时间？
[编程题]聊天
这道题目可以查看区间是否有重合，对于A的某个区间[a,b]，B的某个区间[c+t,d+t]，如果
(c+t<=b) && (d+t>=a)成立，就说明区间之间有重合，满足要求
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int p,q,l,r;
vector<pair<int,int>> A;
vector<pair<int,int>> B;
int ans;
bool isOK(int t){
for(int i=0; i<A.size();i++){
for(int j=0; j<B.size();j++){
if(B[j].second+t>=A[i].first && B[j].first+t<=A[i].second){
return true;
}
}
}
return false;
}
void solve(){
for(int t=l; t<=r; t++){
if(isOK(t)){
ans++;
}
}
}
int main(){
while(cin>>p>>q>>l>>r){
ans = 0;
A = vector<pair<int,int>>(p);
B = vector<pair<int,int>>(q);
for(int i=0; i<p; i++){
cin>>A[i].first>>A[i].second;
}
for(int i=0; i<q; i++){
cin>>B[i].first>>B[i].second;
}
solve();
cout<<ans<<endl;
}
return 0;
}
发表于 2016-03-21 19:12:19
回复(7)
直接暴力了 题目意思就是判断是否有重复区间
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
//常量区
const int maxn = 50 + 5, tmax = 1e3 + 5;
int c[maxn], d[maxn], min_x, max_y;
int dp[tmax], tmpdp[tmax];
int p, q, l, r;
//函数区
bool solve(int wake_time){
memcpy(tmpdp, dp, sizeof(dp));
for(int i=0;i<q;i++){
for(int j=c[i]+wake_time; j<=d[i]+wake_time; j++)
tmpdp[j]++;
}
for(int i = min_x; i <= max_y;i++){
if(tmpdp[i]>1) return true;
}
return false;
}
//main函数
int main(){
while(scanf("%d%d%d%d", &p, &q, &l, &r) == 4){
memset(dp, 0, sizeof(dp));
min_x = 1e3+5, max_y = 0;
for(int i = 0; i < p; i++){
int x, y; scanf("%d%d", &x, &y);
min_x = min(min_x, x); max_y = max(max_y, y);
for(int j=x;j<=y;j++) dp[j] += 1;
}
for(int i = 0; i < q; i++){
scanf("%d%d", &c[i], &d[i]);
}
int ans = 0;
for(int i=l; i <= r; i++)
if(solve(i)) ans++;
cout<<ans<<endl;
}
return 0;
}
发表于 2018-10-08 12:45:46
回复(0)
import java.util.Scanner;
public class Mugu3 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
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 i = 0; i < q; i++) {
b[i][0] = scanner.nextInt();
b[i][1] = scanner.nextInt();
}
System.out.println(getUpTime(p, q, l, r, a, b));
}
}
public static int getUpTime(int p, int q, int l, int r, int[][] a, int[][] b) {
int count = 0;
for (int i = l; i <= r; i++) {
if(isProperTime(a, b, i)){
count++;
}
}
return count;
}
public static boolean isProperTime(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] + d;
int b2 = B[j][1] + d;
if (b1 <= a2 && b2 >= a1)
return true;
}
}
return false;
}
}
发表于 2016-09-28 09:23:53
回复(3)
def isIn(d1, d2, i):
for x in d1:
for y in d2:
if not (x[0] > y[1] + i or x[1] < y[0] + i):
return True
while 1:
try:
s = raw_input()
except:
break
p, q, l, r = map(int, s.split())
d1, d2, cnt = [], [], 0
for _ in range(p):
d1.append(map(int, raw_input().split()))
for _ in range(q):
d2.append(map(int, raw_input().split()))
for i in range(l, r + 1):
if isIn(d1, d2, i):
cnt += 1
print cnt
发表于 2017-05-04 11:27:27
回复(0)
// 不知道为什么本地没问题，这里没有输出？// 用滑动窗口做的二重循环 复杂度O(n*r) #include <iostream> #include <vector> //#include <sstream> //#include <unordered_map> //#include <string> using namespace std; int main(){ int ans=0,maxa=0,maxb=0; int p,q,l,r; cin>>p>>q>>l>>r; vector<pair<int,int>> a(p); vector<pair<int,int>> b(q); for (int pi=0;pi<p;pi++){ cin>>a[pi].first>>a[pi].second; maxa=maxa>a[pi].second?maxa:a[pi].second; } for (int qi=0;qi<q;qi++){ cin>>b[qi].first>>b[qi].second; maxb=maxb>b[qi].second?maxb:b[qi].second; } int*arange=new int[maxa+1]; int*brange=new int[maxb+1];//防止越界 for (int pi=0;pi<p;pi++){ for (int i=a[pi].first;i<=a[pi].second;i++){ arange[i]=1; } } for (int qi=0;qi<q;qi++){ for (int i=b[qi].first;i<=b[qi].second;i++){ brange[i]=1; } } for (int j=l;j<=r;j++){ for (int i=0;i<maxb&&i+j<maxa;i++){ if (arange[i+j]+brange[i]==2){ ans++; break; } } }
delete [] arange,brange; cout << ans<<endl; //system("pause"); return 0; }
编辑于 2017-03-14 21:28:00
回复(2)
A和B两人的空闲时间区间[ai,bi]，[ci+t,di+t]只要有一个存在重叠两人就能有公共的休闲时刻聊天
def judge(t): for i in range(p): for j in range(q): # 有一个休闲的时间段重叠就行，包括了边界点，要保留等号 if intervalB[j][0] + t <= intervalA[i][1] and intervalB[j][1] + t >= intervalA[i][0]: return True return False if __name__ == "__main__": while True: try: p, q, l, r = map(int, input().strip().split()) intervalA, intervalB = [], [] for _ in range(p): intervalA.append(list(map(int, input().strip().split()))) for _ in range(q): intervalB.append(list(map(int, input().strip().split()))) cnt = 0 for t in range(l, r + 1): if judge(t): cnt += 1 print(cnt) except: break
发表于 2021-04-11 18:11:38
回复(0)
遍历每个时间，判断是否能说上话
不能说话的情况是：b睡的时间<a起床时间 (或) b起床时间>a睡觉时间；这里暂且把每小段时间当成清醒时间，其余时间都是睡觉。。。。取非之后，就是可以说话，直接返回就好。
import java.util.Scanner;
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 l=sc.nextInt();
int r=sc.nextInt();
int [][] a=new int [p][2];
int [][] b=new int [q][2];
for(int i=0;i<p;i++){
a[i][0]=sc.nextInt();
a[i][1]=sc.nextInt();
}
for(int i=0;i<q;i++){
b[i][0]=sc.nextInt();
b[i][1]=sc.nextInt();
}
int count=0;
for(int i=l;i<=r;i++){
if(cantalk(a,b,i))
count++;
}
System.out.println(count);
}
}
public static boolean cantalk(int [][] a,int [][] b,int t){
for(int i=0;i<b.length;i++){
for(int j=0;j<a.length;j++){
if(!(b[i][0]+t>a[j][1])&&!(b[i][1]+t<a[j][0]))
return true;
}
}
return false;
}
}
编辑于 2018-07-03 16:44:42
回复(0)
时间复杂度O((l-r+1)*(p+q))
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
int result = 0;
int p = scan.nextInt();
int q = scan.nextInt();
int l = scan.nextInt();
int r = scan.nextInt();
int[] a = new int[p];
int[] b = new int[p];
int[] c = new int[q];
int[] d = new int[q];
for (int i = 0; i < p; i++) {
a[i] = scan.nextInt();
b[i] = scan.nextInt();
}
for (int i = 0; i < q; i++) {
c[i] = scan.nextInt();
d[i] = scan.nextInt();
}
for (int i = l; i <= r; i++) {
if (isProperTime(a, b, c, d, i)) {
result++;
}
}
System.out.println(result);
}
}
private static boolean isProperTime(int[] a, int[] b, int[] c, int[] d, int delay) {
int i = 0, j = 0, p = a.length, q = b.length;
while (i < p && j < q) {
if (c[j] + delay < b[i] && d[j] + delay > a[i]) {
return true;
}
if (c[j] + delay >= b[i]) {
i++;
} else {
j++;
}
}
return false;
}
}
发表于 2018-03-06 19:48:07
回复(0)
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int main()
{ int p,q,l,r; while(cin>>p>>q>>l>>r) { vector<vector<int> > va(p, vector<int>(2, 0)); vector<vector<int> > vb(q, vector<int>(2, 0)); for(int i=0;i<p;i++) cin>>va[i][0]>>va[i][1]; for(int i=0;i<q;i++) cin>>vb[i][0]>>vb[i][1]; int count = 0; for(int t=l;t<=r;t++) { bool flag = false; for(int i=0;i<q;i++) { if(flag) break; for(int j=0;j<p;j++) if(vb[i][0]+t >= va[j][0] && vb[i][0]+t <= va[j][1] || vb[i][1]+t >= va[j][0] && vb[i][1]+t <= va[j][1]) { count++; flag = true; break; } } } cout<<count<<endl; } return 0;
}
发表于 2017-10-14 01:34:32
回复(0)
#include<iostream>
#include<vector>
using namespace std;
int main(){
int p, q, l, r;
while (cin >> p >> q >> l >> r){
vector<vector<int>> va(p, vector<int>(2, 0));
vector<vector<int>> vb(q, vector<int>(2, 0));
for (int i = 0; i < p; ++i)
cin >> va[i][0] >> va[i][1];
for (int i = 0; i < q; ++i)
cin >> vb[i][0] >> vb[i][1];
int cnt = 0;
for (int t = l; t <= r; ++t){
bool flag = false;
for (int i = 0; i < q; ++i){
if (flag)
break;
for (int j = 0; j < p; ++j){
if (vb[i][0] + t >= va[j][0] && vb[i][0] + t <= va[j][1] ||
vb[i][1] + t >= va[j][0] && vb[i][1] + t <= va[j][1]){
cnt++;
flag = true;
break;
}
}
}
}
cout << cnt << endl;
}
return 0;
}
发表于 2017-05-18 10:09:48
回复(0)
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)
判断区间是否有交集，代码如下：
#include<iostream>
#include<unordered_map>
using namespace std;
using MyHash = unordered_map<int, bool>;
int main(void)
{
int p, q, l, r;
while (cin >> p >> q >> l >> r) {
int a[p], b[p];
for (int i = 0; i < p; ++i) {
cin >> a[i] >> b[i];
}
int c[q], d[q];
for (int i = 0; i < q; ++i) {
cin >> c[i] >> d[i];
}
MyHash hash_cnt;
for (int i = 0; i < p; ++i) {
for (int j = 0; j < q; ++j) {
int tp1 = a[i] - d[j];
int tp2 = b[i] - c[j];
if (tp2 > r) tp2 = r;
if (tp1 < l) tp1 = l;
for (int i = tp1; i <= tp2; ++i) {
hash_cnt.insert(MyHash::value_type(i, true));
}
}
}
cout << hash_cnt.size() << endl;
}
return 0;
}
编辑于 2016-08-29 09:35:23
回复(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)
#include <iostream>
#include <algorithm>
using namespace std;
intmain(){
intp,q,l,r;
while(cin>>p>>q>>l>>r)
{
inta[51],b[51],c[51],d[51];
bool n[1001]={false};
intn1,m1;
intsum=0;
for(inti=0;i<p;i++)
cin>>a[i]>>b[i];
for(inti=0;i<q;i++)
cin>>c[i]>>d[i];
for(inti=0;i<q;i++)
{
for(intj=0;j<p;j++)
{
n1=-1;
m1=-1;
if(d[i]<=a[j])
{
n1=a[j]-d[i];
m1=b[j]-c[i];
}
else
if(c[i]<=b[j])
{
n1=0;
m1=b[j]-c[i];
}
if(n1!=-1&&m1!=-1){
for(intk=n1;k<=m1;k++)
n[k]=true;
}
}
}
for(inti=l;i<=r;i++)
{
if(n[i])
sum++;
}
cout<<sum<<endl;
}
return0;
}
发表于 2015-09-28 23:15:29
回复(1)
// 抛砖引玉
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
// insert code here...
int q, p, l, r;
int a[50][2], b[50][2];
// int c[1000] = {0};
int total;
while (cin >> q >> p >> l >> r) {
total = 0;
int c[1000] = {0};
for (int i = 0; i < q; i++) {
cin >> a[i][0] >> a[i][1];
}
for (int i = 0; i < p; i++) {
cin >> b[i][0] >> b[i][1];
}
for (int i = l; i <= r; i++) {
for (int j = 0; j < q; j++) {
for (int k = 0; k < p; k++) {
if ((b[k][0] + i <= a[j][0] && b[k][1] + i >= a[j][0]) ||
(b[k][0] + i <= a[j][1] && b[k][1] + i >= a[j][1]) ||
(b[k][0] + i <= a[j][0] && b[k][1] + i >= a[j][1]) ||
(b[k][0] + i >= a[j][0] && b[k][1] + i <= a[j][1]))
c[i] = 1;
}
}
total += c[i];
}
cout << total << endl;
}
return 0;
}
发表于 2015-09-22 17:27:28
回复(3)
问题信息
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
