源兄毎日1題の第12弾POJ 2456
976 ワード
http://poj.org/problem?id=2456
問題:c個の乳牛をn個の格子に入れ、隣接する乳牛間の距離を最小値で最大にし、あるいは乳牛の分布をできるだけ平均させる.
構想:一定の距離が存在し、ちょうどこの間隔ですべての乳牛を置くことができることを満たすことができ、その前の間隔はすべての格子を完全に利用していない.この間隔より大きいとすべての乳牛を置くことができない.私たちはこの距離を二分して私たちが望んでいる答えを見つけることができます.
この問題は二分思想の入門問題で、二分というものは不思議で、一定の条件を満たすとき、1つの区間でlogレベルのクエリーを行うことができます.
どのような構造が二分の役に立つのでしょうか.一つだけ考えなければならないことがあります.私はある位置の状態を知ってから、この位置よりもこの位置の前後関係を解くことができるかどうかを確定することができます.たとえば,単調な性質を持つ数列,ある点で状態が変わる関数などがある.
問題:c個の乳牛をn個の格子に入れ、隣接する乳牛間の距離を最小値で最大にし、あるいは乳牛の分布をできるだけ平均させる.
構想:一定の距離が存在し、ちょうどこの間隔ですべての乳牛を置くことができることを満たすことができ、その前の間隔はすべての格子を完全に利用していない.この間隔より大きいとすべての乳牛を置くことができない.私たちはこの距離を二分して私たちが望んでいる答えを見つけることができます.
この問題は二分思想の入門問題で、二分というものは不思議で、一定の条件を満たすとき、1つの区間でlogレベルのクエリーを行うことができます.
どのような構造が二分の役に立つのでしょうか.一つだけ考えなければならないことがあります.私はある位置の状態を知ってから、この位置よりもこの位置の前後関係を解くことができるかどうかを確定することができます.たとえば,単調な性質を持つ数列,ある点で状態が変わる関数などがある.
#include
#include
#include
#include
#include
using namespace std;
int n,c;
int coor[100005];
int judge(int m){
if(m>coor[n-1])
return 0;
int s = 0,t = c-1,v = m;
while(s