题面:
题意:一共有m个工人,第i个工人一共工作wi天,一共有n天,第i天共有di个人工作,且每个人只要开始工作就必须连续工作w天,每次工作结束,至少休息h天才开始下一次工作,现在题目给n,m,w,h,数组w[i]和数组d[i],问有没有合理的安排方案满足所给条件,按输入顺序输出每个人的工作安排,每行表示一个人的工作安排,按照日期升序输出每次工作开始的天数
思路:把d[i]数组预处理成有几个从第i天开始的工作,然后把所有人推进一个优先队列,下一个时间最近的工作分给剩余工作量最大的人,若有几人剩余工作量相同则分给上一个工作结束时间最早的人
代码:
#include<iostream>
#include <cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<functional>
#include <unordered_map>
#include<queue>
#include<cmath>
#include<unordered_map>
#include<fstream>
#include<ctime>
using namespace std;typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 2050;typedef struct node
{int id;int wi;int now;bool operator <(const node &x) const{if (x.wi == wi)return now > x.now;return wi < x.wi;}
}node;node a;
int d[maxn];
vector<int> ans[maxn];
int m, n, w, h;
priority_queue<node> q;
int as = 0, ds = 0;int main()
{scanf("%d%d%d%d", &m, &n, &w, &h);for (int i = 1; i <= m; i++){scanf("%d", &a.wi);as += a.wi;a.wi /= w;a.id = i;a.now = 1;q.push(a);}for (int i = 1; i <= n; i++) {scanf("%d", &d[i]);ds += d[i];}if (as != ds){printf("-1\n");return 0;}for (int i = 1; i <= n; i++){for (int j = 1; j < w && i + j <= n; j++)d[i + j] -= d[i];}for (int i = 1; i <= n; i++) {if (d[i] < 0){printf("-1\n");return 0;}}for (int i = 0; i < w - 1; i++){if (d[n - i] != 0){printf("-1\n");return 0;}}for (int i = 1; i <= n;) {queue<node> tmp;node k;int f = 0;while (!q.empty()){k = q.top();q.pop();if (k.now<=i) {ans[k.id].push_back(i);d[i]--;k.wi--;f = 1;k.now = i + w + h;}tmp.push(k);if (!d[i])break;}while (!tmp.empty()){k = tmp.front();tmp.pop();if (k.wi)q.push(k);}if (!f)break;while (!d[i] && i <= n)i++;if (q.empty())break;}if (!q.empty()) {printf("-1\n");return 0;}for (int i = 1; i <= n; i++){if (d[i] != 0){printf("-1\n");return 0;}}printf("1\n");for (int i = 1; i <= m; i++){int len = ans[i].size();for (int j = 0; j < len - 1; j++){printf("%d ", ans[i][j]);}printf("%d\n", ans[i][len - 1]);}
}