[luogu] P1638 逛画展 二分答案||尺取法

前言

一开始就有点歪,尺取法待补 传送门 :

思路

一开始以为是二分答案,二分左端点毕竟如果是二分金钱的话

时间复杂度( l o g n ∗ m ∗ n log_n*m*n logn​∗m∗n) 感觉会超时

结果二分左端点没二分出来,实践证明没有单调性

所以又乖乖滚回去二分金钱,显然对于已有金钱,我们只需要判断左右两边是否有满足

答案的即可,所以我们直接按照这个模拟即可

CODE

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
#define endl '\n'


typedef pair pii;
unordered_map mp;
const int N  = 1e6+10;
int a[N];

int n,m,cnt;
int ansl,ansr ;

bool check(int x)
{
	int cnt = 0 ;
	mp.clear();

	for(int i=1;in>>m;

	for(int i=1;i>a[i];

	 int l = 1, r= n ;
	// while(l+1>1;
		// if(check(mid))
		// r = mid;
		// else
		// l =mid;
	// }
	// cout