题目
点这里看题目。
分析
首先考虑只有洗衣机的情况。我们可以想到,当前洗衣任务结束越早的洗衣机应该被先用,因此可以用堆来动态维护。
再考虑有烘干机的情况。很显然,越晚洗完的衣服应该越早烘干。因此我们可以按照处理洗衣机的方法,给衣服按照结束洗衣时间从大到小分配烘干机。
用一个堆对洗衣机和烘干机各维护一次,时间\(O(k\log_2n)\)。
代码
#include <queue>
#include <cstdio>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 5, MAXK = 1e6 + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
struct ele
{
LL t; int indx;
ele() { t = indx = 0; }
ele( LL T, int I ) { t = T, indx = I; }
bool operator < ( const ele &b ) const { return ! ( t < b.t ); }
};
priority_queue<ele> q;
LL resA[MAXK], resB[MAXK];
int a[MAXN], b[MAXN];
int K, N, M;
int main()
{
ele h;
read( K ), read( N ), read( M );
for( int i = 1 ; i <= N ; i ++ ) read( a[i] );
for( int i = 1 ; i <= M ; i ++ ) read( b[i] );
for( int i = 1 ; i <= N ; i ++ ) q.push( ele( a[i], i ) );
for( int i = 1 ; i <= K ; i ++ )
{
h = q.top(), q.pop();
resA[i] = h.t, q.push( ele( h.t + a[h.indx], h.indx ) );
}
while( ! q.empty() ) q.pop();
for( int i = 1 ; i <= M ; i ++ ) q.push( ele( b[i], i ) );
for( int i = K ; i ; i -- )
{
h = q.top(), q.pop();
resB[i] = h.t, q.push( ele( h.t + b[h.indx], h.indx ) );
}
LL ans = 0;
for( int i = 1 ; i <= K ; i ++ ) ans = MAX( ans, resA[i] + resB[i] );
write( ans ), putchar( '\n' );
return 0;
}