记录编号	191281	评测结果	AAAAAAAAAA
题目名称	[POJ1275]出纳员的雇佣	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2015-10-06 20:56:59	内存使用	0.29 MiB

#include<cstdio>
#include<deque>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<iostream>
using namespace std;
const int SIZEN=40,maxn=0x7fffffff/2;
int N,R[SIZEN],w[SIZEN],P=24;
deque<pair<int,int> > s[SIZEN];
void read()
{
	for(int i=0;i<24;i++)
		scanf("%d",&R[i]);
	scanf("%d",&N);
	memset(w,0,sizeof(w));
	for(int i=1;i<=N;i++)
	{
		int t;
		scanf("%d",&t);
		w[t]++;
	}
}
void gragh(int x)
{
	for(int i=0;i<=P;i++) s[i].clear();
	for(int i=1;i<P;i++) s[i].push_back(make_pair(i-1,0));
	s[0].push_back(make_pair(P,0));
	for(int i=1;i<P;i++) s[i-1].push_back(make_pair(i,w[i]));
	s[P].push_back(make_pair(0,w[0]));
	for(int i=8;i<P;i++) s[i].push_back(make_pair(i-8,-R[i]));
	for(int i=0;i<=7;i++) s[i].push_back(make_pair(i+16,x-R[i]));
	s[23].push_back(make_pair(P,-x));
	s[P].push_back(make_pair(23,x));
}
bool spfa(int x)
{
	int sw[SIZEN],cnt[SIZEN]={0};
	bool inq[SIZEN];
	deque<int> Q;
	for(int i=0;i<=P;i++) sw[i]=maxn,inq[i]=0;
	sw[P]=0;inq[P]=1;Q.push_back(P);cnt[P]++;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();inq[x]=0;
		for(int i=0;i<s[x].size();i++)
		{
			int v=s[x][i].first,w=s[x][i].second;
			if(sw[v]>sw[x]+w)
			{
				if(!inq[v])
				{
					if(cnt[v]>=P) return 0;
					inq[v]=1;cnt[v]++;
					Q.push_back(v);
				}
				sw[v]=sw[x]+w;
			}
		}
	}
	if(sw[23]!=x) return 0;
	return 1;
}
int work()
{
	int l=0,r=N+1;
	while(l<r)
	{
		int mid=(l+r)/2;
		gragh(mid);
		if(spfa(mid)) r=mid;
		else l=mid+1;
	}
	return l;
}
int main()
{
	freopen("cashieremployment.in","r",stdin);
	freopen("cashieremployment.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T)
	{
		T--;
		read();
		int ans=work();
		if(ans==N+1) printf("No Solution\n");
		else printf("%d\n",ans);
	}
	return 0;
}