[abc] AtCoder Regular Contest 075 D - Widespread 二分答案

前言

奇奇怪怪的 c h e c k check check 传送门 :

思路

首先想到的是 贪心 , 但是自证一下 因为有 B B B的影响在下一步选取 A A A的时候可能不是最优解,所以不做考虑

我们可以通过二分 攻击次数来做, 因为 B B B的伤害是独立的 也就是你 A A A不管选

哪个 他都会扣除 B B B的生命值,所以我们 C h e c k Check Check的时候,只需要判断 有多少个超标 的 也就是要中心爆破的BOSS 然后不断二分即可

Mycode

// Problem: D - Widespread
// Contest: AtCoder - AtCoder Regular Contest 075
// URL: https://atcoder.jp/contests/arc075/tasks/arc075_b
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//��һ�δ��Ϻ�վ֮�� ��Ϊʹ��#define int long long TLE���¿��˺ܾõ�ʱ�� ���˼���ģ��
//����ʹ�ø��ӵ�ģ��

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define int long long
#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)

typedef priority_queue  Pri_m;
typedef pair pii;
typedef vector VI;
map mp;

const int N  = 1e5+10;
int a[N],A,B;
int n;

bool check(int x){
	int t =  B*x;
	int cnt = 0 ;
	
	for(int i=1;i t) //说明需要在这里爆破
			cnt+=(a[i] - t+A-1)/A;
			
		/*
		这里其实同理于
		if(a[i] - t)%A == 0
		
		else
		cnt += (a[i] -t )/A +1;
		
		
		*/
	}
	return cnt>n;
	cin>>A>>B;
	A-=B;
	
	
	for(int i=1;i>a[i];
	
	int l = 1 ,  r =  1e9;
	while(l >1;
		if(check(mid) ) r= mid-1;
		else l = mid+1;
	}
	
	cout