4.1 题意描述
花花家的超市是 24 小时营业的，现在需要招聘收银员。
超市每个小时都需要不同数量的收银员，用 ai 表示一天中 i 点到 i + 1 点这一小时内需要
的收银员数量，特别地 a23 表示 23 点到次日 0 点需要的收银员数量。每个时刻可以有多于 ai
的收银员工作，但是绝对不能少于 ai 人。现有 n 人应聘，每个人愿意从一个特定的整点开始
连续工作 8 小时。花花想知道最少要招多少人。
若无解请输出 -1。
4.2 输入格式
输入第一行包括一个正整数 t，表示测试组数。
接下来 2t 行，每两行表示一个测试点：
其中第一行包括 24 个非负整数 ai(i 2 [0; 23])，表示至少需要 ai 个人从 i 点工作到 i + 1
点（特别地 a23 表示 23 点到次日 0 点）。
第二行包括 24 个非负整数 bi(i 2 [0; 23])，表示应聘的人中有 bi 个人愿意从 i 点工作到
i + 1 点（特别地 b23 表示 23 点到次日 0 点）。
4.3 输出格式
对于每个测试组，输出一行包含一个整数表示最少要招多少人或 -1。
4.4 样例输入
1
0 0 0 0 0 0 0 0 2 2 1 5 2 0 3 1 1 4 1 4 2 6 3 3
1 1 1 0 1 0 0 0 0 1 3 2 0 0 4 0 3 0 1 0 0 2 0 0
4.5 样例输出
12
4.6 样例解释
一种最优的招聘方案为：
0 0 1 0 1 0 0 0 0 0 2 2 0 0 0 0 3 0 1 0 0 2 0 0
4.7 数据规模与约定
• 对于 50% 的数据： n ≤ 20; t = 1；
• 另有 20% 的数据： n ≤ 100; t = 1；
• 另有 20% 的数据： n ≤ 500；
• 对于所有编号为奇数的数据： ai = 0; i 2 [0; 7]；
• 对于 100% 的数据： n ≤ 1000; ∑bi = n; 0 ≤ ai ≤ n; t ≤ 10。
/*
查分约束系统，做过的题并不多，所以写起来很费事。我们很容易想到前缀和，前缀和中
①s[i-1]<=s[i]
②s[i-8]+a[i]<=s[i](i>8)
③s[i+16]+a[i]-s[24]<=s[i]
④s[i]-b[i]<=s[i-1]
求最长路
然而我们发现，③并不满足查分约束系统的形式，我们考虑到枚举s[24]，使s[24]等于一个数，注意这里不能用二分，为什么？比正解大的数并不能保证他的成立，因为由过大的s[24]退出来的其他s是错误的，但如果s[24]恰巧是正解，就不会出现这个问题
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const int maxn = ;
int read(){
char ch=getchar();
int x=,f=;
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
}
struct edge{
int v;
int w;
int nxt;
}e[maxn*];
int T,a[maxn],b[maxn];
int vis[maxn],d[maxn],flag;
int head[maxn],cnt;
void ins(int u,int v,int w){
cnt++;
e[cnt].v = v;
e[cnt].w = w;
e[cnt].nxt = head[u];
head[u] = cnt;
}
bool spfa(int s){
flag++;
queue<int> q;
for(int i = ;i <= ;i++){
d[i] = -;
}
d[] = ;
q.push();
vis[] = flag;
int now,to;
while(!q.empty()){
now = q.front();
q.pop();
//cout<<now<<" "<<d[now]<<endl;
for(int i = head[now];i;i = e[i].nxt){
if(d[e[i].v] < d[now] + e[i].w){
d[e[i].v] = d[now] + e[i].w;
if(d[e[i].v] > s)return false;
if(vis[e[i].v] != flag){
vis[e[i].v] = flag;
q.push(e[i].v);
//cout<<now<<" "<<e[i].v<<" "<<d[now]<<" "<<e[i].w<<" "<<d[e[i].v]<<endl; }
}
}
vis[now] = ;
}
return true;
}
bool check(int s){
//cout<<s<<endl;
cnt = ;
for(int i = ;i <= ;i++){
head[i] = ;
}
for(int i = ;i <= ;i++) ins(i-,i,a[i]);
for(int i = ;i <= ;i++) ins(i+,i,a[i]-s);
for(int i = ;i <= ;i++) ins(i-,i,);
for(int i = ;i <= ;i++) ins(i,i-,-b[i]);
ins(,,s);
ins(,,-s);
return spfa(s);
}
void dvd(){
int l = ,r = ,mid,ans;
while(){
if(l > ){
cout<<-<<endl;
break;
}
if(check(l)){
cout<<l<<endl;
break;
}else{
l++;
}
}
}
int main(){
freopen("cashier.in","r",stdin);
freopen("cashier.out","w",stdout);
T = read();
while(T--){
for(int i = ;i <= ;i++) a[i] = read();
for(int i = ;i <= ;i++) b[i] = read();
dvd();
}
return ;
}