備注:
對(duì)于30%的數(shù)據(jù)有N≤15。
對(duì)于70%的數(shù)據(jù)有N≤2000，M≤50000。
對(duì)于100%的數(shù)據(jù)有N≤20000，M≤100000。

算法知識(shí)點(diǎn)：二分，染色法判斷二分圖
復(fù)雜度：O((N + M)logC)

解題思路：
將罪犯當(dāng)做點(diǎn)，罪犯之間的仇恨關(guān)系當(dāng)做點(diǎn)與點(diǎn)之間的無向邊，邊的權(quán)重是罪犯之間的仇恨值。
那么原問題變成：將所有點(diǎn)分成兩組，使得各組內(nèi)邊的權(quán)重的最大值盡可能小。

我們?cè)?[0, 10^9]之間枚舉最大邊權(quán) limitlimit，當(dāng) limitlimit 固定之后，剩下的問題就是：

判斷能否將所有點(diǎn)分成兩組，使得所有權(quán)值大于 limitlimit 的邊都在組間，而不在組內(nèi)。也就是判斷由所有點(diǎn)以及所有權(quán)值大于 limitlimit 的邊構(gòu)成的新圖是否是二分圖。
判斷二分圖可以用染色法，時(shí)間復(fù)雜度是 O(N + M)O(N+M)，其中 NN 是點(diǎn)數(shù)，MM 是邊數(shù)。

為了加速算法，我們來考慮是否可以用二分枚舉 limit， 假定最終最大邊權(quán)的最小值是 Ans:
那么當(dāng) limit \in [ans, 10^9]limit∈[ans,10 9 ] 時(shí)，所有邊權(quán)大于 limit 的邊，必然是所有邊權(quán)大于 Ans 的邊的子集，因此由此構(gòu)成的新圖也是二分圖。
當(dāng) limit∈[0,ans?1] 時(shí)，由于 ans 是新圖可以構(gòu)成二分圖的最小值，因此由大于 limitlimit 的邊構(gòu)成的新圖一定不是二分圖。
所以整個(gè)區(qū)間具有二段性，可以二分出分界點(diǎn) ans 的值。
時(shí)間復(fù)雜度分析:

總共二分 logClogC 次，其中 CC 是邊權(quán)的最大值，每次二分使用染色法判斷二分圖，時(shí)間復(fù)雜度是 O(N + M)，其中 N 是點(diǎn)數(shù)，M 是邊數(shù)。因此總時(shí)間復(fù)雜度是 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;
}

方法：二分（算次數(shù)）+差分

備注:
對(duì)于 10%的數(shù)據(jù)，有 1 ≤ n，m ≤ 10；
對(duì)于 30%的數(shù)據(jù)，有 1 ≤ n，m ≤ 500；
對(duì)于 50%的數(shù)據(jù)，有 1 ≤ n，m ≤ 5,000；
對(duì)于 70%的數(shù)據(jù)，有 1 ≤ n，m ≤ 10,000；
對(duì)于 100%的數(shù)據(jù)，有 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 天剩余的教室數(shù)分別為0，3，2，3。
第2 份訂單要求第2 天到第4 天每天提供3 個(gè)教室，而第3 天剩余的教室數(shù)為2，因此無法滿足。分配停止，通知第2個(gè)申請(qǐng)人修改訂單。

備注:
對(duì)于10%的數(shù)據(jù)，有1≤n,m≤10；
對(duì)于30%的數(shù)據(jù)，有1≤n,m≤1000；
對(duì)于70%的數(shù)據(jù)，有1≤n,m≤105；
對(duì)于100%的數(shù)據(jù)，有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

說明
將與起點(diǎn)距離為 2 和14 的兩個(gè)巖石移走后，最短的跳躍距離為 4（從與起點(diǎn)距離17的巖石跳到距離 21的巖石，或者從距離 21 的巖石跳到終點(diǎn)）。

備注:
對(duì)于20%的數(shù)據(jù)，0 ≤ M ≤ N ≤ 10。
對(duì)于50%的數(shù)據(jù)，0 ≤ M ≤ N ≤ 100。
對(duì)于100%的數(shù)據(jù)，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;
}