F. Fair Distribution

F. Fair Distribution

18界浙江省赛

1）题目大意：

有n个机器人和m个能量棒，每次操作可以杀掉一个机器人或者增加一个能量棒。问最少几次操作可以使得n'个机器人平分m'个能量棒。

2）思路：

从暴力到整数分块 。

暴力思路：枚举1到n每一个机器人的情况，算出第一个比b大的i的倍数，取min。

ll getceil(ll x , ll y){
	return x / y + (x % y ? 1 : 0) ;
}

ll solve(){

	ll a , b ;
	cin >> a >> b ;
	
	if(b % a == 0) return 0 ;
	if(a > b) return a - b ;
	ll ans = INF ;
	
	for(int i = 0 ; a - i > 0 ; i ++ ){//i是操作次数
		ll opBar = getceil(b , a - i) * (a - i) - b ;
		ans = min(ans , i + opBar) ;
	}
	return ans ;
}

枚举1到n一定会超时，所以采用整数分块。

对于整除，x/y的答案是有块状的性质的（ceil和floor都有），所以我们对于某一块区间里的除数不用全部去操作，而是可以直接用端点来做。

ll getceil(ll x , ll y){//x/y向上取整的公式 
	return (x + y - 1) / y ;
}

ll solve(){

	ll a , b ;
	cin >> a >> b ;
	
	if(b % a == 0) return 0 ;
	if(a >= b) return a - b ;
	
	ll ans = INF ;

	for(ll l = 1 , r ; l <= a ; l = r + 1){ 
		r = (b - 1) / ((b  - 1) / l) ;//向下取整区间分块
		ans = min(ans , getceil(b , l) * l - b + a - l) ;
	}
	
	return ans ;
}

3）扩展和总结：

需要枚举n/i的答案时就可以用整数分块

复杂度2根n

向下取整的分块：

for (ll l = 1, r; l <= m; l = r + 1) {
    r = n / (n / l);  
}

向上取整的分块：

for(ll l = 1 , r ; l <= a ; l = r + 1){ 
		r = (b - 1) / ((b  - 1) / l) ;//向下取整区间分块
	}