题解分析

by hansang

本题要求最小数目，因此采用最长路算法。

变量说明：

• r[i]: 要求有多少人在工作
• x[i]: 实际有多少人开始工作
• s[i]: x[i]的前缀和
• c[i]: 最多可以有多少人在工作

约束条件：

• 0 <= x[i] <= c[i] => 0 <= s[i] - s[i-1] <= c[i]
  • 0 <= s[i] - s[i-1] => s[i-1] + 0 <= s[i] (1)[1, 24]
  • s[i] - s[i-1] <= c[i] => s[i] - c[i] <= s[i-1] (2)[1, 24]
• 连续8天的工作人数和 >= r[i]：x[i-7] + x[i-6] + x[i-5] + x[i-4] + x[i-3] + x[i-2] + x[i-1] >= r[i] => s[i] - s[i-8] >= r[i] => s[i-8] + r[i] <= s[i] (3)[9, 24]
• 连续17天的工作人数和 >= r[i]：x[i+17] + x[i+18] + x[i+19] + ... + x[24] + x[1] + x[2] + ... + x[i] >= r[i] => s[24] - s[i+16] + s[i] >= r[i] => s[i+16] + r[i] - s[24] <= s[i] (4)[1, 8]

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int R[N], c[N], d[N], t[N];
struct node { int x, d; };
vector<node> G[N];
queue<int> Q; bool v[N];

int spfa() {
    memset(v, 0, sizeof(v));
    memset(t, 0, sizeof(t));
    memset(d, -0x3f, sizeof(d));
    Q.push(0); v[0] = 1; d[0] = 0;
    while (!Q.empty()) {
        int x = Q.front(); Q.pop(); v[x] = 0;
        for (node i : G[x]) {
            int y = i.x, w = i.d;
            if (d[y] < d[x] + w) {
                d[y] = d[x] + w;
                if (!v[y]) {
                    Q.push(y); v[y] = 1;
                    t[y]++; if (t[y] > 25) return 0;
                }
            }
        }
    }
    return 1;
}

bool check(int x) {
    memset(G, 0, sizeof(G));
    for (int i = 1; i <= 24; i++) G[i-1].push_back({i, 0}); // (1)
    for (int i = 1; i <= 24; i++) G[i].push_back({i-1, -c[i]}); // (2)
    for (int i = 9; i <= 24; i++) G[i-8].push_back({i, R[i]}); // (3)
    for (int i = 1; i <= 8; i++) G[i+16].push_back({i, R[i] - x}); // (4)
    G[0].push_back({24, x}); G[24].push_back({0, -x}); // s[0] + x = s[24]
    return spfa();
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        memset(c, 0, sizeof(c));
        for (int i = 1; i <= 24; i++) scanf("%d", &R[i]);
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            int x; scanf("%d", &x);
            c[x+1]++;
        }
        int l = 0, r = n, p = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid)) r = mid - 1, p = mid;
            else l = mid + 1;
        }
        if (p == -1) printf("No Solution\n");
        else printf("%d\n", p);
    }
    return 0;
}

by hansang:

/* by hansang
求最小数目，所以跑最长路 
r[i]:要求有多少人在工作
x[i]:实际有多少人开始工作
s[i]:x[i]的前缀和 
c[i]:最多可以有多少人在工作 
 
0<=x[i]<=c[i] => 0<=s[i]-s[i-1]<=c[i]
0<=s[i]-s[i-1]      =>      s[i-1]+0<=s[i] (1)[1, 24]
s[i]-s[i-1]<=c[i]     =>    s[i]-c[i]<=s[i-1] (2)[1, 24]

x[i-7]+x[i-6]+x[i-5]+x[i-4]+x[i-3]+x[i-2]+x[i-1]+x[i-1]>=r[i]
s[i]-s[i-8]>=r[i]     =>    s[i-8]+r[i]<=s[i] (3)[9, 24]

x[i+17]+x[i+18]+x[i+19]+...+x[24]+x[1]+x[2]+...+x[i]>=r[i]
s[24]-s[i+16]+s[i]>=r[i] => s[i+16]+r[i]-s[24]<=s[i] (4)[1, 8]
*/
#include<bits/stdc++.h>
using namespace std;
const int N=30;
int R[N], c[N], d[N], t[N];
struct node{int x, d;};
vector<node> G[N];
queue<int> Q; bool v[N];
int spfa(){
	memset(v, 0, sizeof(v));
	memset(t, 0, sizeof(t));
	memset(d, -0x3f, sizeof(d));
	Q.push(0); v[0]=1; d[0]=0;
	while(!Q.empty()){
		int x=Q.front(); Q.pop(); v[x]=0;
		for(node i: G[x]){
			int y=i.x, w=i.d;
			if(d[y]<d[x]+w){
				d[y]=d[x]+w;
				if(!v[y]){
					Q.push(y); v[y]=1;
					t[y]++; if(t[y]>25) return 0;
				}
			}
		}
	}
	return 1;
}
bool check(int x){
	memset(G, 0, sizeof(G));
	for(int i=1; i<=24; i++) G[i-1].push_back({i, 0}); //(1) 
	for(int i=1; i<=24; i++) G[i].push_back({i-1, -c[i]}); //(2) 
	for(int i=9; i<=24; i++) G[i-8].push_back({i, R[i]}); //(3) 
	for(int i=1; i<=8; i++) G[i+16].push_back({i, R[i]-x}); //(4) 
	G[0].push_back({24, x}); G[24].push_back({0, -x}); //s[0]+x=s[24]
	return spfa();
}
int main(){
	int T; scanf("%d", &T);
	while(T--){
		memset(c, 0, sizeof(c));
		for(int i=1; i<=24; i++) scanf("%d", &R[i]);
		int n; scanf("%d", &n);
		for(int i=1; i<=n; i++){
			int x; scanf("%d", &x);
			c[x+1]++;
		}
		int l=0, r=n, p=-1;
		while(l<=r){
			int mid=(l+r)/2;
			if(check(mid)) r=mid-1, p=mid;
			else l=mid+1;
		}
		if(p==-1) printf("No Solution\n");
		else printf("%d\n", p);
	} 
	return 0;
}