0724提高组2-二分(直播）

备注:
对于30%的数据有N≤15。
对于70%的数据有N≤2000，M≤50000。
对于100%的数据有N≤20000，M≤100000。

算法知识点：二分，染色法判断二分图
复杂度：O((N + M)logC)

解题思路：
将罪犯当做点，罪犯之间的仇恨关系当做点与点之间的无向边，边的权重是罪犯之间的仇恨值。
那么原问题变成：将所有点分成两组，使得各组内边的权重的最大值尽可能小。

我们在 [0, 10^9]之间枚举最大边权 limitlimit，当 limitlimit 固定之后，剩下的问题就是：

判断能否将所有点分成两组，使得所有权值大于 limitlimit 的边都在组间，而不在组内。也就是判断由所有点以及所有权值大于 limitlimit 的边构成的新图是否是二分图。
判断二分图可以用染色法，时间复杂度是 O(N + M)O(N+M)，其中 NN 是点数，MM 是边数。

为了加速算法，我们来考虑是否可以用二分枚举 limit， 假定最终最大边权的最小值是 Ans:
那么当 limit \in [ans, 10^9]limit∈[ans,10 9 ] 时，所有边权大于 limit 的边，必然是所有边权大于 Ans 的边的子集，因此由此构成的新图也是二分图。
当 limit∈[0,ans−1] 时，由于 ans 是新图可以构成二分图的最小值，因此由大于 limitlimit 的边构成的新图一定不是二分图。
所以整个区间具有二段性，可以二分出分界点 ans 的值。
时间复杂度分析:

总共二分 logClogC 次，其中 CC 是边权的最大值，每次二分使用染色法判断二分图，时间复杂度是 O(N + M)，其中 N 是点数，M 是边数。因此总时间复杂度是 O((N + M)logC)。

代码：

#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define oo INT_MAX
#define ll long long
#define db double
#define mp(a, b) make_pair(a, b)
#define met(a, b) memset(a, b, sizeof(a))
#define maxn 100000+10
#define _rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define _rev(i, a, b) for(int i = (a); i >= (b); --i)
#define _for(i, a, b) for(int i = (a); i < (b) ;++i)
using namespace std;
const int N = 20010,M = 200010 ;

int n,m;
int h[N],e[M],w[M],ne[M],idx;
int color[N];
    
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool dfs(int u,int c,int limit)
{
    color[u]=c;
    for(int i=h[u];~i;i=ne[i])///
    {
        if(w[i] <= limit) continue;
        int j = e[i];
        if(color[j])
        {
            if(color[j]==c)
                return false;
        }
        else if(!dfs(j,3-c,limit)) 
            return false;
    }
    return true;
}

bool check(int limit)
{
    memset(color,0,sizeof color);
    for(int i=1;i<=n;i++)
    {
        if(color[i] == 0)
        {
            if(!dfs(i,1,limit))
                return false;
        }
    }
    return true;
}


int main()
{
    
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }

    int l = 0,r = 1e9;
    while(l<r)//二分
    {
        int mid = (l+r) >> 1;
        if(check(mid)) r = mid;
        else l = mid+1;
    }
    printf("%d\n",l);
    return 0;
}

方法：二分（算次数）+差分

备注:
对于 10%的数据，有 1 ≤ n，m ≤ 10；
对于 30%的数据，有 1 ≤ n，m ≤ 500；
对于 50%的数据，有 1 ≤ n，m ≤ 5,000；
对于 70%的数据，有 1 ≤ n，m ≤ 10,000；
对于 100%的数据，有 1 ≤ n，m ≤ 200,000，0 < wi, vi ≤ 106，0 < S ≤ 1012，1 ≤ Li ≤ Ri ≤ n。

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cstdio>
using namespace std;

typedef long long ll;
const int N = 200020;
ll sum[N];
ll S;
int w[N],v[N];
int l[N],r[N];
int cnt[N];
int n,m;

ll get(int W)
{

    for(int i=1;i<=n;i++)
        if(w[i] >= W)
        {
            sum[i] = sum[i-1] + v[i];
            cnt[i] = cnt[i-1] + 1;
        }
        else
        {
            sum[i] = sum[i-1];
            cnt[i] = cnt[i-1];
        }
        ll res = 0;
        for(int i=0;i<m;i++)
        {
            res+=(cnt[r[i]]-cnt[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
        }
    return res;
}

int main()
{
    scanf("%d%d%lld",&n,&m,&S);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&w[i],&v[i]);
    for(int i=0;i<m;i++)
        scanf("%d%d",&l[i],&r[i]);

    int l=0,r=1e6+1;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(get(mid)>=S) l=mid;
        else r=mid-1;
    }
    printf("%lld\n",min(abs(get(r)-S),abs(S-get(r+1))));
    return 0;
}

示例1
输入
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
输出
-1
2
说明
第1 份订单满足后，4 天剩余的教室数分别为0，3，2，3。
第2 份订单要求第2 天到第4 天每天提供3 个教室，而第3 天剩余的教室数为2，因此无法满足。分配停止，通知第2个申请人修改订单。

备注:
对于10%的数据，有1≤n,m≤10；
对于30%的数据，有1≤n,m≤1000；
对于70%的数据，有1≤n,m≤105；
对于100%的数据，有1≤n, m≤106, 0≤ri, dj≤109, 1≤sj≤tj≤ n。

怎么做：

#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int maxn=1000010;
int n,m;
int r[maxn],d[maxn],s[maxn],t[maxn];
ll b[maxn];

bool check(int k)
{
    for(int i=1;i<=n;i++)
        b[i] = r[i];
    for(int i=1;i<=k;i++)
    {
        b[s[i]] -=d[i];
        b[t[i]+1] += d[i];
    }

    ll res = 0;
    for(int i=1;i<=n;i++)
    {
        res+=b[i];
        if(res < 0)return true;
    }

    return false;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&r[i]);
    for(int i=n;i;i--)
        r[i] -= r[i-1];

    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&d[i],&s[i],&t[i]);

    int l=1,r=m;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }

    if(check(r))
    {
        puts("-1");
        printf("%d\n",r);
    }
    else puts("0");

    return 0;
}

示例1
输入
25 5 2
2
11
14
17
21
输出
4

说明
将与起点距离为 2 和14 的两个岩石移走后，最短的跳跃距离为 4（从与起点距离17的岩石跳到距离 21的岩石，或者从距离 21 的岩石跳到终点）。

备注:
对于20%的数据，0 ≤ M ≤ N ≤ 10。
对于50%的数据，0 ≤ M ≤ N ≤ 100。
对于100%的数据，0 ≤ M ≤ N ≤ 50,000，1 ≤ L ≤ 1,000,000,000。

怎么做

#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int maxn=50010;
int L,n,m;
int d[maxn];

bool check(int mid)
{
    int last = 0,cnt = 0;
    for(int i=1;i<=n;i++)
        if(d[i]-last < mid) cnt++;
        else last = d[i];
    return cnt<=m;///
}

int main()
{
    scanf("%d%d%d",&L,&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&d[i]);
    d[++n] = L;

    int l=1,r=1e9;
    while(l<r)
    {
        int mid = l+r+1 >>1;
        if(check(mid)) l = mid;
        else r=mid - 1;
    }

    printf("%d\n",r);

    return 0;
}