首页 > 代码库 > Exams（二分求左界+贪心）
Exams（二分求左界+贪心）
用力戳我直达原题：D - Exams
题意:
有N天和M门课程。
接下来给你N天的行为，0表示这一天只能预习，[1,m]表示这一天可以考这门课（当然这一天你也可以选择不考或者预习）。
接下来给你M个数cost[i]，代表第i门课需要预习cost[i]天才能PASS。
求从第一天起算，最少需要几天才能PASS所有功课，如果N天都PASS不了，则输出-1。
做法：
1.先判断用N天能否PASS，不能就输出-1。
2.low = m, high = n。求左界。
3-1 judge的时候，一门课肯定越慢考越容易通过，所以从mid开始找，第一次遇到的功课标记vis[day[i]]。
3-2 如果day[i]等于0或者day[i]已经访问过了，也就是说这一天能用来复习，sum++；
3-3 如果sum >= 预习所需要的总时间sum_cost，且所有课程都有安排考试，说明时间充裕，返回true。
3-4 第一天肯定只能拿来复习不能拿来考试，所以sum初始化为1，遍历从 mid -> 2。
3-5 从mid开始找到第一个不是0的数，因为这些天的复习是无效的，后面无考试了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <bits/stdc++.h>using namespace std;int day[100100];int sum_cost = 0;bool vis[100100];int n, m, x;bool judge(int mid) { memset(vis, false, sizeof(vis)); while(day[mid] == 0) mid--; int sum = 1; //累加预习时间 int tot = 0; //累加安排考试科目数 for(int i = mid; i >= 2; i--) { int cur = day[i]; if(vis[cur] || cur == 0) sum++; else tot++, vis[cur] = true; } return (sum >= sum_cost && tot == m);}int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", day+i); for(int i = 1; i <= m; i++) scanf("%d", &x), sum_cost += x; //累计最终需要多少天 if(judge(n) == false) { puts("-1"); return 0; } int low = m, high = n; while(low < high) { int mid = low + high >> 1; if(judge(mid)) high = mid; else low = mid + 1; } printf("%d\n", high);} |
Exams（二分求左界+贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。