问题 C: Frosh Week
时间限制: 4 Sec 内存限制: 128 MB提交: 145 解决: 63
[提交][状态][讨论版][命题人:admin]
题目描述
Professor Zac is trying to finish a collection of tasks during the first week at the start of the term. He knows precisely how long each task will take, down to the millisecond. Unfortunately, it is also Frosh Week. Zac’s office window has a clear view of the stage where loud music is played. He cannot focus on any task when
music is blaring.
The event organizers are also very precise. They supply Zac with intervals of time when music will not be playing. These intervals are specified by their start and end times down to the millisecond.
Each task that Zac completes must be completed in one quiet interval. He cannot pause working on a task when music plays (he loses his train of thought). Interstingly, the lengths of the tasks and quiet intervals are such that it is impossible to finish more than one task per quiet interval!
Given a list of times ti (in milliseconds) that each task will take and a list of times Lj (in milliseconds) specifying the lengths of the intervals when no music is being played, what is the maximum number of tasks that Zac can complete?
music is blaring.
The event organizers are also very precise. They supply Zac with intervals of time when music will not be playing. These intervals are specified by their start and end times down to the millisecond.
Each task that Zac completes must be completed in one quiet interval. He cannot pause working on a task when music plays (he loses his train of thought). Interstingly, the lengths of the tasks and quiet intervals are such that it is impossible to finish more than one task per quiet interval!
Given a list of times ti (in milliseconds) that each task will take and a list of times Lj (in milliseconds) specifying the lengths of the intervals when no music is being played, what is the maximum number of tasks that Zac can complete?
输入
The first line of input contains a pair of integers n and m, where n is the number of tasks and m is the
number of time intervals when no music is played. The second line consists of a list of integers t1,t2,...,tn indicating the length of time of each task. The final line consists of a list of times L1,L2,... ,Lm indicating the length of time of each quiet interval when Zac is at work this week.
You may assume that 1≤n;m≤200,000 and 100,000≤ti,Lj≤199,999 for each task i and each quiet interval j.
number of time intervals when no music is played. The second line consists of a list of integers t1,t2,...,tn indicating the length of time of each task. The final line consists of a list of times L1,L2,... ,Lm indicating the length of time of each quiet interval when Zac is at work this week.
You may assume that 1≤n;m≤200,000 and 100,000≤ti,Lj≤199,999 for each task i and each quiet interval j.
输出
Output consists of a single line containing a single integer indicating the number of tasks that Zac can accomplish from his list during this first week.
样例输入
5 4
150000 100000 160000 100000 180000
190000 170000 140000 160000
样例输出
4
很简单的模拟题，开始我想的是存下所有的时间，然后sort，把各自大的放前面，进行比较，虽然担心了时间，但是看到4s还是交了，果不其然t了。Orz
后面一看，不就1e5到2e5的时间范围吗，直接用值哈希，跑一遍。
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 int task[100001]; 6 int work_num[100001]; 7 const int limit = 100000; 8 9 int main() 10 { 11 int n,m; 12 scanf("%d%d",&n,&m); 13 int temp; 14 memset(task,0,sizeof(task)); 15 memset(work_num,0,sizeof(work_num)); 16 for(int i=0;i<n;i++) 17 { 18 scanf("%d",&temp); 19 task[temp-limit]++; 20 } 21 for(int i=0;i<m;i++) 22 { 23 scanf("%d",&temp); 24 work_num[temp - limit]++; 25 } 26 int ans = 0; 27 int cnt = 0; 28 for(int i=limit;i>=0;i--) 29 { 30 if(work_num[i])cnt+=work_num[i]; 31 if(cnt != 0) 32 { 33 if(task[i]) 34 { 35 int minn = min(task[i],cnt); 36 ans += minn; 37 cnt -= minn; 38 } 39 } 40 } 41 printf("%d ",ans); 42 } 43 44 /************************************************************** 45 Problem: 5129 46 User: DP18 47 Language: C++ 48 Result: 正确 49 Time:68 ms 50 Memory:2476 kb 51 ****************************************************************/