JZOJ 4336 Rabbit

考虑对每种胡萝卜和干草建点，从超级源点向第 i 种胡萝卜连容量为 mi 的边，从第 j 种干草向超级汇点连容量为 nj 的边，所有 M×N 组胡萝卜向干草连容量为 1 的边。
答案即最大流。

这样显然过不了（

将 {mi},{ni} 分别升序，设 Sm(i)=i∑j=1mj,Sn(i)=i∑j=1nj。
根据最大流最小割定理，易知需要最小化 Sm(x)+Sn(y)+(M−x)(N−y)。
枚举 x，易知当 y 为最大的满足 ny≤M−x 的 y 时上式取最小值。
双指针或者在值域意义上维护 Sn 均可。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2.5e6;
int n,m,a[N + 5],ad,b[N + 5],bd;
int c[2][N + 5],cnt;
long long s[2][N + 5],ans = 0x3f3f3f3f3f3f3f3f;
int main()
{
    scanf("%d%d%d%d%d%d",&n,&m,a + 1,&ad,b + 1,&bd),++c[0][a[1]],++c[1][b[1]];
    for(register int i = 2;i <= n;++i)
        a[i] = (58LL * a[i - 1] + ad) % (m + 1),++c[0][a[i]];
    for(register int i = 2;i <= m;++i)
        b[i] = (58LL * b[i - 1] + bd) % (n + 1),++c[1][b[i]];
    for(register int i = 0;i <= m;++i)
        for(;c[0][i];--c[0][i],++cnt,s[0][cnt] = s[0][cnt - 1] + i);
    for(register int i = 1;i <= n;++i)
        s[1][i] = s[1][i - 1] + (long long)c[1][i] * i,c[1][i] += c[1][i - 1];
    for(register int i = 0;i <= n;++i)
        ans = min(ans,s[0][i] + s[1][n - i] + (long long)(n - i) * (m - c[1][n - i]));
    printf("%lld\n",ans);
}