问题描述
试题编号: | 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编译器上
内容来源于网络如有侵权请私信删除
- 还没有人评论,欢迎说说您的想法!