记录编号	290266	评测结果	AAAAAAAAAA
题目名称	[POJ1275]出纳员的雇佣	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2016-08-06 06:08:40	内存使用	0.29 MiB

/*
	设num[ i ]为i时刻能够开始工作的人数，x[ i ]为 第 i 时刻实际雇佣的人数，那么x[ I ]<=num[ I ]。 
	设r[ i ]（输入的每一时刻所需的人数）为i时刻至少需要工作的人数，于是有如下关系： 
	x[ I-7 ]+x[ I-6 ]+x[ I-5 ]+x[ I-4 ]+x[ I-3 ]+x[ I-2 ]+x[ I-1 ]+x[ I ]>=r[ I ]
	设s[ I ]=x[ 1 ]+x[ 2 ]…+x[ I ]，得到 
	0<=s[ I ]-s[ I-1 ]<=num[ I ]， 0<=I<=23 
	s[ I ]-s[ I-8 ]>=r[ I ]， 8<=I<=23    建立关系
	s[ 23 ]+s[ I ]-s[ I+16 ]>=r[ I ]， 0<=I<=7 建立可以循环的关系 
	对于以上的几组不等式，我们采用一种非常笨拙的办法处理这一系列的不等式(其实也是让零乱的式子变得更加整齐，易于处理)。
	首先我们要明白差分约束系统的应用对象（它通常针对多个二项相减的不等式的）
	于是我们将上面的所有式子都转化成两项未知项在左边，另外的常数项在右边，且中间用>=连接的式子，即:
	s[ I ] - s[ I-1 ] >= 0            (0<=I<=23) 
	s[ I-1 ] - s[ I ] >= -num[ I ]       (0<=I<=23) 
	s[ I ]-s[ I-8 ]>=r[ I ]         (8<=I<=23) 
	s[ I ]-s[ I+16 ]>=r[ I ]-s[ 23 ]  (0<=I<= 7)
	S[23] - 0 >= sum;sum为雇佣的出纳员总数
*/
//好麻烦的关系转换，，，对差分约束不会再有爱了。。。
#include <cstdio>
#include <cstring>
using namespace std;
template<typename T>inline void read(T &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!'); if( ch == '-' ) ch=getchar(),flag = true;
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if( flag ) x=-x;
}
int n,m,p,ecnt,T;
int dis[30],cnt[30],r[30],t[30];
const int INF = 1e9;
int to[100],head[30],he[30],ne[100]={0},w[100]={0};
inline void add(int u,int v,int c){
	to[++ecnt] = v;
	w[ecnt] = c;
	ne[ecnt] = head[u];
	head[u] = ecnt;
}
int Q[100],qhead = 1,qtail = 99,size = 0;
bool flag[100];
inline int top(){
	int x = Q[qhead];
	if( ++qhead == 100 )qhead=1;
	--size;
	flag[x] = false;
	return x;
}
inline void push_front(int x){
	flag[x] = true;
	++size;
	if( !(--qhead) ) qhead=99;
	Q[ qhead ] = x;
}
inline void push_back(int x){
	flag[x] = true;
	++size;
	if(++qtail == 100) qtail = 1;
	Q[qtail] = x;
}
inline bool spfa(int mid){
	for(int i = 0;i <= 24; ++i) dis[i] = -INF,cnt[i] = 0;
	cnt[0] = 1;dis[0] = 0;
	push_back(0);
	while( size ) for(int x=top(),i=head[x];i;i=ne[i])
	if( dis[ to[i] ] < dis[x] + w[i]){
		dis[ to[i] ] = dis[x] + w[i];
		if( !flag[to[i]] ){
			if( ++cnt[to[i]] > 24) return 0;
			if( size && dis[Q[qhead]] <= dis[to[i]]) push_front(to[i]);
			else push_back(to[i]);
		}
	}
	if(dis[24] == mid) return 1;
	return 0;
}
 
int main(){
	freopen("cashieremployment.in","r",stdin);
	freopen("cashieremployment.out","w",stdout);
	read<int>(T);
	while(T--){
		for(int i=1;i<=24;++i) read<int>(r[i]);
		for(int i=0;i<=24;++i) t[i] = head[i] = 0;
		read<int>(n);
		ecnt = 0;
		int x;
		for(int i=1;i<=n;++i)  read<int>(x),t[x+1]++;
		for(int i=1;i<=24;++i) add(i-1,i,0),add(i,i-1,-t[i]);
		for(int i=0;i<=24;++i) he[i] = head[i];
		int ans = -1,L = 0,R = n;
		while(L<=R){
			int mid = (L+R)>>1;ecnt=48;
			for(int i=0;i<=24;++i)head[i]=he[i];
			add(0,24,mid);
			for(int i=1;i<=8;++i)add(i+16,i,r[i]-mid);
			for(int i=9;i<=24;++i)add(i-8,i,r[i]);
			if(spfa(mid)) ans = mid,R = mid-1;
			else L=mid+1;
		}
		if(ans == -1) printf("No Solution\n");
		else printf("%d\n",ans);
	}
	return 0;
}