hdu1529 Cashier Employment[差分约束+二分答案]

这题是一个类似于区间选点，但是有一些不等式有三个未知量参与的情况。

依题意，套路性的，将小时数向右平移1个单位后，设$f_i$为前$i$小时工作的人数最少是多少，$f_{24}$即为所求。设$c_i$为第$i$小时可选人数，$lim_i$为要求人数下限。

$0\le f_i-f_{i-1}\le c_i$，保证合法
$i\ge 8$时，$f_i-f_{i-8}\ge lim_i$
$i<8$时，由于环形，$f_i+(f_{24}-f_{i+16})\ge lim_i$，但这个不好处理，因为这不是一个二元关系，有第三个未知数参与。不过分析可知这些不等式中参与的第三个量是同一个，那么我们可以暴力枚举这个$f_{24}$，然后化为二元，再建图看合不合法。
使用上一条的方法时，注意限制$f_{24}-f_0=枚举的数$

事实上，答案满足可二分性，于是改为二分答案，跑正环检验即可。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #define dbg(x) cerr << #x << " = " << x <<endl

 #define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=,INF=0x3f3f3f3f;

 struct thxorz{int to,nxt,w;}G[N];

 int Head[],tot;

 int cnt[],lim[];

 int T,n,L,R;

 inline void Addedge(int x,int y,int z){G[++tot].to=y,G[tot].nxt=Head[x],Head[x]=tot,G[tot].w=z;}

 int dis[],inq[],rel[];

 #define y G[j].to

 inline bool spfa(){

     queue<int> q;

     for(register int i=;i<=;++i)q.push(i),dis[i]=,inq[i]=,rel[i]=;

     while(!q.empty()){

         int x=q.front();q.pop();

         inq[x]=;//dbg(x);

         for(register int j=Head[x];j;j=G[j].nxt)if(MAX(dis[y],dis[x]+G[j].w)){

             rel[y]=rel[x]+;if(rel[y]>=)return ;//dbg(y);

             if(!inq[y])inq[y]=,q.push(y);

         }

     }

     return ;

 }

 #undef y

 inline bool check(int mid){

     memset(Head,,sizeof Head),tot=;

     for(register int i=;i<=;++i)Addedge(i-,i,),Addedge(i,i-,-cnt[i]);

     for(register int i=;i<=;++i)Addedge(i-,i,lim[i]);

     for(register int i=;i<;++i)Addedge(i+,i,lim[i]-mid);

     Addedge(,,mid),Addedge(,,-mid);

     return spfa();

 }

 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);

     read(T);while(T--){

         for(register int i=;i<=;++i)read(lim[i]);

         memset(cnt,,sizeof cnt);

         read(n);for(register int i=,x;i<=n;++i)read(x),cnt[x+]++;

         L=,R=n+;//dbg(check(1)),dbg(check(2)),dbg(check(3)),dbg(check(4)),dbg(check(5));

         while(L<R){

             int mid=L+R>>;

             if(check(mid))R=mid;

             else L=mid+;

         }

         if(L<=n)printf("%d\n",L);

         else puts("No Solution");

     }

     return ;

 }

一道弱智小题耗我半小时。。

RE记录：差分约束题建边老是容易在Addedge处写倒掉。注意本题$n$的意味，不要混淆成点数。

总结：第三元参入不等式，二分答案检验。

巴特西

hdu1529 Cashier Employment[差分约束+二分答案]

最新文章

热门文章