二分查找+贪心-CodeForces 732D-Exams

- 日理万妓 2022-05-17 10:46 218阅读 0赞

*  # 二分查找+贪心-CodeForces 732D-Exams #

--------------------

*  ## 题目链接：[D. Exams][] ##
 *  ## 思路：二分+贪心 ##

题目大意是给定考试天数和科目数，及对应的考试安排表、每个科目所需复习时间，求出**最小完成考试的天数**，如果在考试规定天数内完成不了，输出-1

真的想不到用二分。。。

**通过二分，不断搜索直到找到最优区间，而最优区间的判定，用到贪心的思想**

在该区间内，把**考试都安排在该区间内的最后一场该考试，这样就有足够时间留给自己复习，如果这样安排都没办法满足可利用复习时间大于等于剩余科目准备时间和，就说明没办法在该区间内完成所有考试**。

从区间最右到最左进行安排，在**此过程中需减去无法利用的空闲时间及对考完试科目标记已考状态。**

![70][]

**无法利用空闲时间：**在考完一科后（图中笑脸），在待考和已考之间存在一段空闲时间，**但该段时间无法进行复习**，所以需要从可利用复习时间中减去）

由于每次都会去除无法利用的空闲时间，所以该区间内可完成考试的条件是 **可利用时间=0**

*  ## 代码： ##

#include<iostream>	
    using namespace std;
    
    #define MAX_SIZE 100005
    
    int n, m;
    int Time_Sum;
    
    int Schedule[MAX_SIZE];
    int Prepare_Time[MAX_SIZE];
    
    bool BSearch(int Floor)
    {
    	bool Check[MAX_SIZE] = { 0 };
    	int Free_Time = Floor - m;		//区间内可支配的空闲时间
    	int Temp_Sum = Time_Sum;		//完成全部考试所需准备时间
    
    	for (int i = Floor; i >= 1; i--)
    	{
    		if (Schedule[i] == 0 || Check[Schedule[i]])		//清除鸡肋时间：在某科考试之后的空闲时间，不能用于复习
    		{
    			Free_Time--;
    			continue;
    		}
    
    		//遇到考试
    		if (Free_Time >= Temp_Sum)		//当前剩余的空闲时间必须大于等于剩余考试的准备时间
    		{
    			Check[Schedule[i]] = true;			//标记该科目已考
    			Temp_Sum -= Prepare_Time[Schedule[i]];		//考完，减掉该科的的准备时间
    		}
    		else
    			return false;		//不足以准备后面的考试
    	}
    	return Free_Time == 0;
    }
    
    
    int main()
    {
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++)
    		cin >> Schedule[i];
    	Time_Sum = 0;
    	for (int i = 1; i <= m; i++)
    	{
    		cin >> Prepare_Time[i];
    		Time_Sum += Prepare_Time[i];
    	}
    	int Left = 1, Right = n;
    	while (Left < Right)			//二分查找
    	{
    		int Mid = (Left + Right) / 2;
    		if (BSearch(Mid))
    			Right = Mid;
    		else
    			Left = Mid + 1;
    	}
    	
    	if (BSearch(Right))
    		cout << Right << endl;
    	else
    		cout << "-1" << endl;
    	return 0;
    }

[D. Exams]: http://codeforces.com/problemset/problem/732/D
[70]: /images/20220517/b4f0a33d648c40bea8ca7d3f18df9ecd.png