二分答案 get ！
普通：
传送门
二分 + 差分
int n,m,ans;
int a[MAXN],b[MAXN];
struct node{
int L,R,w;
}query[MAXN];
void work(int L, int R);
void check(int L, int R, int mid)
{
int flag = 1;
for(int i=1;i<=n;i++)
{
if(a[i]-b[i] < 0)
{
work(L,mid);
flag = 0;
break;
}
}
if(flag) work(mid+1,R);
}
void work(int L, int R)
{
if(L >= R)
{
if(L==n || R==n) cout << "0";
else cout << "-1" << endl << L;
return;
}
memset(b,0,sizeof(b));
int mid = (L+R)/2;
for(int i=1;i<=mid;i++)
{
int l = query[i].L;
int r = query[i].R+1;
int w = query[i].w;
b[l] += w; b[r] -= w;
}
for(int i=1;i<=n;i++)
b[i] += b[i-1];
check(L,R,mid);
}
int main(void)
{
ios:: sync_with_stdio(false);
cin >> n >> m;
for(int i=1;i<=n;i++)
cin >> a[i];
for(int i=1;i<=m;i++)
cin >> query[i].w >> query[i].L >> query[i].R;
work(0,n);
return 0;
}
独秀：
传送门
01分数规划 + 01背包
结合公式
如果结果
否则二分左区间
#define max(a,b) a>b ? a : b;
int n,W;
int t[300],w[300];
int dp[10005];
bool check(int mid)
{
memset(dp,0x80,sizeof(dp));
int temp = dp[W];
dp[0] = 0;
for(int i=1;i<=n;i++)
for(int j=W;j>=0;j--)
if(temp != dp[j])
dp[min(W,j+w[i])]=max(dp[min(W,j+w[i])],dp[j]+t[i]-(long long)w[i]*mid);
return dp[W] >= 0;
}
int main(void)
{
cin >> n >> W;
for(int i=1;i<=n;i++)
{
cin >> w[i] >> t[i];
t[i] *= 1000;
}
int L=0,R=0x3f3f3f3f;
while(L <= R)
{
int mid = (L+R)/2;
if(check(mid)) L = mid+1;
else R = mid-1;
}
cout << L-1;
return 0;
}
提高：
传送门
二分 + 树上差分 + 树剖 + 线段树 + 吸氧 终于过了。。。
其实难点主要是在二分上，不过我还是从头讲起吧
给定一棵树，和树上的某些链，去掉某个边权，使最长链最短。
求链长，我选择了 树剖 + 线段树 其实差分也可以，不过正好想练习一下树剖。
对于最长链最短，自然是二分，不过，二分什么呢？
二分链长，如果去掉一条边后比 mid 小了，那 mid 左移，否则右移。
现在，思考一下它的正确性，（顺便捋一捋思路）
一. 对于 mid 左侧的链，长度自然不可能大于 mid
二. 对于右侧的链，在减去某条边后可能比 mid 小，所以不好判断
1. 对于上面的情况，考虑最长的链，最长链减去一条边后若小于mid，那所有右侧的边肯定都小于 mid
2. 若大于 mid 则说明 mid 还可以右移
三、对于选择减去哪条边，显然应该选所有 mid 右侧链都经过的边，
这样统一减去才可以比较，
如果选了没有全部经过的边，则无法将 mid 与右侧所有的链统一比较。
四、根据上面，如果没有一条边被所有 mid 右侧的链经过，则说明 mid 可以右移。
可以这样想：
对于一条特殊的链（即有一条边其他链通过，而它没有），
由于所有链是递增的，在减去边长前后它的排名可能会发生变动，
但只可能往右走，所以答案不可能是在 mid 到它之间的链，所以 mid 要右移。看着代码可能会好懂一些
#define _L k<<1
#define _R k<<1|1
int n,m,cnt,maxn,tot;
int head[MAXN],W[MAXN];
int size[MAXN],FA[MAXN],son[MAXN],dep[MAXN];
int DFN[MAXN],Top[MAXN],Rnk[MAXN];
int num[MAXN],len[MAXN];
struct Node{
int x,y,lca,w;
bool operator< (Node a) const{
return w < a.w;
}
}Link[MAXN];
struct NOde{
int L,R,w;
}tree[4*MAXN];
inline void build(int L, int R, int k)
{
tree[k].L = L;
tree[k].R = R;
if(L == R)
{
tree[k].w = W[Rnk[L]];
return;
}
int mid = (L+R)>>1;
build(L,mid,_L);
build(mid+1,R,_R);
tree[k].w = tree[_L].w+tree[_R].w;
}
inline int query(int l, int r, int k)
{
int ans=0;
int L = tree[k].L;
int R = tree[k].R;
if(L>=l && R<=r) return tree[k].w;
int mid = (L+R)>>1;
if(l <= mid) ans = query(l,r,_L);
if(r > mid) ans += query(l,r,_R);
return ans;
}
inline void dfs1(int u, int fa)
{
dep[u] = dep[fa]+1;
size[u] = 1;
FA[u] = fa;
for(int k=head[u];k;k=map[k].next)
{
int v = map[k].to;
if(v == fa) continue;
W[v] = map[k].w;
dfs1(v,u);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
}
inline void dfs2(int u, int top)
{
DFN[u] = ++cnt;
Top[u] = top;
Rnk[cnt] = u;
if(!son[u]) return;
dfs2(son[u],top);
for(int k=head[u];k;k=map[k].next)
{
int v = map[k].to;
if(v==FA[u] || v==son[u]) continue;
dfs2(v,v);
}
}
inline void dfs3(int u, int fa)
{
for(int k=head[u];k;k=map[k].next)
{
int v = map[k].to;
if(v == fa) continue;
dfs3(v,u);
num[u] += num[v];
if(num[u]==tot) maxn = max(maxn,W[u]);
}
}
inline int LCA(int x, int y, int i)
{
int nx = Top[x];
int ny = Top[y];
while(nx != ny)
{
if(dep[nx] < dep[ny])
{
swap(nx,ny);
swap( x, y);
}
Link[i].w += query(DFN[nx],DFN[x],1);
x = FA[nx];
nx = Top[x];
}
if(x == y) return x;
if(dep[x] > dep[y]) swap(x,y);
Link[i].w += query(DFN[son[x]],DFN[y],1);
return x;
}
inline bool check(int mid)
{
memset(num,0,sizeof num);
maxn = 0;
tot = 0;
for(int i=m;i>0;i--)
{
if(Link[i].w <= mid) break;
num[Link[i].x]++;
num[Link[i].y]++;
num[Link[i].lca] -= 2;
tot++;
}
if(!tot) return 1;
dfs3(1,0);
return Link[m].w-maxn <= mid;
}
inline void binary()
{
int L = 0;
int R = Link[m].w;
while(L <= R)
{
int mid = (L+R)>>1;
if(check(mid)) R = mid-1;
else L = mid+1;
}
cout << L;
}
int main(void)
{
cin >> n >> m;
for(int i=1;i<n;i++)
{
int u,v,w;
cin >> u >> v >> w;
add(u,v,w);
add(v,u,w);
}
cnt = 0; dfs1(1,0); dfs2(1,1);
build(1,n,1);
for(int i=1;i<=m;i++)
{
cin >> Link[i].x >> Link[i].y;
Link[i].lca = LCA(Link[i].x,Link[i].y,i);
}
sort(Link+1,Link+1+m);
binary();
return 0;
}翻墙：
codechef 2018-Oct-t4
翻到阿三的网站上去找到了一道不错的二分题目。
跨区传送！
要二分什么东西？ 当然是答案！
先算出全部使用糖的花费，即
然后呢？找
这里比较贪心，如果所有的气球都用完了，但仍有某一天的花费超过了
注意边界问题
struct node{
long long A,B,AB;
bool operator <(node a) const{
return AB < a.AB;
}
}day[MAXN];
bool check(long long mid)
{
long long tm = m;
for(int i=n;i>0;i--)
{
if(day[i].AB <= mid) break;
if((day[i].AB-mid)%day[i].B != 0)
tm -= (day[i].AB-mid)/day[i].B+1;
else
tm -= (day[i].AB-mid)/day[i].B;
if(tm < 0) return 0; //这里没有等于0，因为如果等于0则mid可以尝试性的缩小一些，毕竟要求最大值最小
}
return 1;
}
int main(void)
{
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> day[i].A;
for(int i=1;i<=n;i++)
{
cin >> day[i].B;
day[i].AB = day[i].A*day[i].B;
tot = max(tot,day[i].AB);
}
sort(day+1,day+1+n);
long long L = 0;
long long R = tot;
while(L <= R)
{
long long mid = (L+R)>>1;
if(check(mid)) R = mid-1;
else L = mid+1;
}
cout << L;
return 0;
}