问题描述

试题编号: 201809-2
试题名称: 买菜
时间限制: 1.0s
内存限制: 256.0MB
问题描述:
问题描述
  小H和小W来到了一条街上,两人分开买菜,他们买菜的过程可以描述为,去店里买一些菜然后去旁边的一个广场把菜装上车,两人都要买n种菜,所以也都要装n次车。具体的,对于小H来说有n个不相交的时间段[a1,b1],[a2,b2]...[an,bn]在装车,对于小W来说有n个不相交的时间段[c1,d1],[c2,d2]...[cn,dn]在装车。其中,一个时间段[s, t]表示的是从时刻s到时刻t这段时间,时长为t-s。
  由于他们是好朋友,他们都在广场上装车的时候会聊天,他们想知道他们可以聊多长时间。
输入格式
  输入的第一行包含一个正整数n,表示时间段的数量。
  接下来n行每行两个数ai,bi,描述小H的各个装车的时间段。
  接下来n行每行两个数ci,di,描述小W的各个装车的时间段。
输出格式
  输出一行,一个正整数,表示两人可以聊多长时间。
样例输入
4
1 3
5 6
9 13
14 15
2 4
5 7
10 11
13 14
样例输出
3
数据规模和约定
  对于所有的评测用例,1 ≤ n ≤ 2000, ai < bi < ai+1,ci < di < ci+1,对于所有的i(1 ≤ i ≤ n)有,1 ≤ ai, bi, ci, di ≤ 1000000。
 

【java代码】

package ccf_test_02;
/*思路:
 * 定义一个Time对象,用于存储时间段。
 * 定义一个数组存储时间轴,这里不考虑内存是否浪费,我直接采用最大时间轴存储1000000个时间点
 * 接下来是遍历每一个时间段,时间段落在时间轴上的置+1,
 * 最后是遍历整个时间轴,找到时间点是2的,然后talk++;输出talk
 * 
 * */
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;

public class T201809_2 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Time> timeList = new ArrayList<Time>();
        int[] index = new int[1000000];
        int talk = 0;//可以聊天多长时间
        for(int i = 0;i<n*2;i++){
            timeList.add(new Time(sc.nextInt(),sc.nextInt()));
        }
        sc.close();
        Iterator<Time> it = timeList.iterator();
        while(it.hasNext()){
            Time time = it.next();
            int start = time.getStartTime();
            int end = time.getEndTime();
            for(int i = start;i<end;i++){
                index[i]=index[i]+1;
            }
        }
        
        for(int i = 1;i<index.length;i++){
            if(index[i]==2){
                talk++;
            }
        }
        System.out.print(talk);
    }
}
class Time {
    private int startTime;
    private int endTime;
    public Time(int startTime, int endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }
    public int getStartTime() {
        return startTime;
    }
    public void setStartTime(int startTime) {
        this.startTime = startTime;
    }
    public int getEndTime() {
        return endTime;
    }
    public void setEndTime(int endTime) {
        this.endTime = endTime;
    }
}

将以上代码去掉包名,类名改成Main直接复制到CCF编译器上

 

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!