好久沒做差分限制系統了,有點陌生。
簡述:給定一個數K和若幹個區間Li , Ri(Li可能大于Ri,交換下即可)。|Li|,|Ri|<=10000。要在區間 [ Li , Ri ]上選出 K個點塗上顔色。求數軸上最少的被塗色的點的個數。(簡單起見,假設 Li,Ri>=0)
思路:差分限制系統:
記 S_i 為 [ 0 , i ] 這個區間内染色的點的個數。那麼就有S_Ri - S_( Li-1) >= min( K , Ri - Li + 1)。并且對于任意兩個點i < j,有S_i + j - i >= S_ j,S_i <= S_ j.
于是得到:S_( Li - 1 ) <= S_Ri - min( K, Ri - Li +1);
S_ j <= S_i + j - i.
S_i <= S_ j + 0.
然後連邊的時候,鑒于後面兩個不等式滿足傳遞性,隻要對相鄰的兩個點連一下就好,不需要兩兩連邊。
Ps:初始化所有S_i 的值要相等。然後減掉 min{ S_i },得到非負解。
下面代碼稍微離散的一下。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define clr(A) memset(A,0,sizeof(A))
using namespace std;
int const maxn = 10005;
int const B = 10003;
int N,K;
int b[maxn],e[maxn],w[maxn],tot;
int s[maxn*3];
int a[maxn],sum;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&K,&N);
sum = tot = 0;
int x,y;
for(int i = 1;i<=N;i++)
{
scanf("%d%d",&x,&y);
if(x>y) swap(x,y);
x--;
b[tot] = y, e[tot] = x,w[tot] = -min(K,y-x),tot++;
a[sum++] = x, a[sum++] = y;
}
sort(a,a+sum);a[sum] = maxn;
int cnt = 0;
for(int i = 0;i<sum;i++)
if(a[i] != a[i+1]) a[cnt++]=a[i];
sum = cnt;
for(int i = 1;i<sum;i++)
{
b[tot]=a[i-1],e[tot] = a[i],w[tot] = a[i]-a[i-1],tot++;
b[tot]=a[i],e[tot] = a[i-1],w[tot] = 0, tot++;
}
clr(s);
for(int i = 0;i<sum;i++)
for(int j = 0;j<tot;j++)
s[e[j]+B] = min(s[e[j]+B],s[b[j]+B]+w[j]);
int tmp = s[a[0] + B];
s[a[0] + B] = 0;
printf("%d\n",s[a[sum-1] + B]-tmp);
for(int i = 1;i<sum;i++)
{
s[a[i] + B] -= tmp;
int l = s[a[i] + B] - s[a[i-1] + B];
for(int j = a[i] - l+1;j<=a[i];j++)
printf("%d\n",j);
}
if(T) printf("\n");
}
return 0;
}