秋季学期一起开心讲课-week02-二分，贪心，尺取

56 阅读 0 评论 37 点赞

我是靠谱客的博主传统火龙果，最近开发中收集的这篇文章主要介绍秋季学期一起开心讲课-week02-二分，贪心，尺取，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二分：

①左闭右开二分

//左闭右开 二分 
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 9
int main()
{
	int a[maxn];
	for(int i = 0; i < maxn; i ++)
		scanf("%d",&a[i]);
	sort(a,a+maxn);
	int left = 0;
	int right = maxn;
	int mid;
	int target;
	int flag = 0;
	scanf("%d",&target);
	while(left<right)
	{
		mid = (left+right)/2;
		if(a[mid]<target)
			left = mid + 1;
		else if(a[mid]>target)
			right = mid;
		else 
		{
			flag = 1;
			break;
		}
	 } 
	 if(flag)
		 printf("%d",mid);
	else
		printf("-1");
}

②左闭右闭二分

//左闭右闭 二分 
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 9
int main()
{
	int a[maxn];
	for(int i = 0; i < maxn; i ++)
		scanf("%d",&a[i]);
	sort(a,a+maxn);
	int left = 0;
	int right = maxn - 1;
	int mid;
	int target;
	int flag = 0;
	scanf("%d",&target);
	while(left<=right)//不同的地方 
	{
		//防止溢出 mid = (left)+(right-left)/2; 
		mid = (left+right)/2;
		if(a[mid]<target)
			left = mid + 1;
		else if(a[mid]>target)
			right = mid -1;
		else 
		{
			flag = 1;
			break;
		}
	 } 
	 if(flag)
		 printf("%d",mid);
	else
		printf("-1");
}

尺取：

两个指针，初始状态左指针在最左端，右指针在下一个位置。

首先右指针移动，移动到符合条件的时刻后；

接下来左指针开始移动，移动到刚好不符合目标状态，重复步骤1.

int l,r;        //左右指针
int len;        //数组长度
l = r = 1;      //初始指针
while(l<len){
    // ok() 状态满足要求
    while( r<len && !ok() )
    {
        change();   // change() r右移的状态改变
        r++;
    }
    
    if( !ok() ) break;      // r到最右还不满足要求，算法结束
 
    ans += x;   // 答案处理
    change();   // l右移的状态改变
    l++;
}