贪心： 首先处理出打磨的最优解 然后按时间倒序处理出喷涂的最优解 最后取个max就好了 然后证明不会，如果有dalao会证请私信我 code：

#include <bits/stdc++.h>
using namespace std;

const long long N = 1e6 + 10;

long long n, k, m;

long long a[N], b[N];

void read(){
	cin >> k >> n >> m;
	for(long long i = 1;i <= n; i++) {
		cin >> a[i];
	}
	for(long long i = 1;i <= m; i++) {
		cin >> b[i];
	}
	return ;
}

struct node{
	long long t, v;
	friend bool operator < (node a,node b){
		return a.t > b.t;
	}
}tmp;

node nd(long long t,long long v){
	node x; x.t = t; x.v = v; return x;
}

priority_queue<node> q;

long long aa[N], bb[N];

bool cmp(long long a,long long b){
	return a > b;
} 

void compute(){
	for(long long i = 1;i <= n; i++) {
		q.push(nd(a[i],a[i])); 
	}
	for(long long i = 1;i <= k; i++){
		tmp = q.top(); q.pop();
		aa[i] = tmp.t;
		tmp.t += tmp.v;
		q.push(tmp);
	}
	while(q.size()) q.pop();
	sort(aa+1,aa+1+k);
	for(long long i = 1;i <= m; i++) {
		q.push(nd(b[i],b[i])); 
	}
	long long ans = 0;
	for(long long i = k;i >= 1; i--){
		tmp = q.top(); q.pop();
		ans = max(ans,tmp.t+aa[i]);
		tmp.t += tmp.v;
		q.push(tmp);
	}
	cout << ans;
	return ;
}

int main(){
	read();
	compute();
	return 0;
}

考虑贪心

对于每一个零件，可以将它加工的程序分为两部分

一个是打磨，一个是喷漆

首先考虑打磨

对于一个零件，我们肯定要找到一台机器使得这一台机器当前加工的时间加上再加工一件的时间最小，这可以用堆来实现

然后对于每一个打磨完的零件我们可以考虑让最晚打磨完的零件选择一个喷漆时间最短机器来喷漆

证明当一个序列 $A$ 按照升序排序，另一个序列 $B$ 按照降序排序时，对应位置相加最大值最小：

设序列 $A$ 为升序排列 $(a_1 \leq a_2 \leq …… \leq a_n)$ ，序列 $B$ 为乱序排列 $(b_1,b_2,……b_n)$

对于序列 $B$ 若存在逆序对 $i$ ，$j$ （$i<j$ 且 $b_i < b_j$ ） ，则将他们交换：

原来的和：$a_i+b_i$ 和 $a_j+b_j$

现在的和：$a_i+b_j$ 和 $a_j+b_i$

因为原来和的最大值 $\max(a_i+b_i,a_j+b_j)=a_j+b_j$

现在和的最大值 $\max(a_i+b_j,a_j+b_i)$

因为 $a_i \leq a_j$ 且 $b_i \leq b_j$ 则：

所以我们可以重复以上方式直到 $B$ 为降序排列，且过程中最大值不会增大

所以命题正确

最后统计答案

时间复杂度 $O(k \times \log n)$

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map> 
#define int long long
using namespace std;
const int N=1e6+10;
int k,n,m,p=1,ans=-2e9;
int t[N],a[N],b[N];
struct node{
	int now,id,t;
	bool operator>(const node& b) const{return now+t>b.now+b.t;}
};
priority_queue<node,vector<node>,greater<node> > q1,q2;
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
signed main(){
	k=reads(),n=reads(),m=reads();
	for(int i=1;i<=n;i++){
		a[i]=reads();
		node t;
		t.now=0,t.id=i,t.t=a[i];
		q1.push(t);
	}
	for(int i=1;i<=m;i++){
		b[i]=reads();
		node t;
		t.now=0,t.id=i,t.t=b[i];
		q2.push(t);
	}
	for(int i=1;i<=k;i++){
		node re=q1.top(),af;
		q1.pop();
		int u=re.now,v=re.id;
		t[i]+=u+a[v];
		af=re;
		af.id=v,af.now=u+a[v];
		q1.push(af);
	}
	sort(t+1,t+k+1); 
	for(int i=k;i>=1;i--){
		node re=q2.top(),af;
		q2.pop();
		int u=re.now,v=re.id;
		t[i]+=u+b[v];
		af=re;
		af.id=v,af.now=u+b[v];
		q2.push(af);
		ans=max(ans,t[i]);
	}
	printf("%lld\n",ans);
	return 0;
}

贪心好题。

首先题目能够被分成两部分处理：

• 对所有零件进行打磨
• 对打磨后的零件进行喷涂

解决前者很简单，解决后者略有难度。

首先来解决第一部分问题，也就是让每个零件被打磨完的时间尽可能的靠前（显然不劣），考虑用优先队列存下来每一个打磨机所需要的时间，然后每一次取时间最小的那个机器，令其对某一零件进行打磨，然后把当前时间加上该打磨机消耗的时间再丢回优先队列，进行上述操作 $k$ 次，即可得到每个零件最早能够被打磨完的时间。

$\log^2$ 做法

现在考虑第二部分怎么做。

我发现我不会贪心求答案，所以我直接二分答案，然后把问题转化为可行性判定。

接下来就是最大化每一个喷涂机的使用次数，有一个显然的思路就是让喷涂机喷涂结束的时间与二分的答案 $T$ 相等，然后判断是否存在一个已经被打磨的零件能够进入该喷涂机，选择距离该时间最近的零件显然不劣。然后再令喷涂机结束的时间是当前时间 $-1$，重复上述操作，直至没有零件可以被该喷涂机喷涂，则切换下一个喷涂机，继续重复上述操作（此处应该有图，有时间会补的）。

所以我们想要实现的是添加时间、删除时间、查询某个时间的前驱，显然使用 set 二分可以实现，在套上外层的二分，时间复杂度是 $O(k\log k\log V)$。

$\log$ 做法

考虑上述算法的本质是什么。

我们称一个被打磨的零件在某个时间放入喷涂机喷涂为一个匹配，二分的可行性判定等价于被打磨的零件与喷涂机开始时间之间是否存在由前者向后者的完全匹配（此处应该有图，有时间会补的）。

你发现如果存在某个可行匹配方案，则让所有的喷涂机开始时间换成最后的 $k$ 个时间是不劣的（此处应该有图，有时间会补的）。

你发现最后 $k$ 个喷涂机开始时间与 $T$ 之间的距离是不随 $T$ 的变化而变化的，所以预处理出最后 $k$ 个喷涂机开始时间即可做到单次二分线性判断了（实际上求出该值后可以不用二分就能得到答案）。

而你发现上述课完全套用第一部分的求法，于是你在 $O(k\log k)$ 的时间复杂度内解决该问题。

先不放代码，等我图上了再说。