loj 6035 「雅礼集训 2017 Day4」洗衣服

分析

神仙贪心题

题解

首先我们用t[i]存下第i件洗完的衣服所用的最短时间，

这个直接用优先队列贪心就好

先把洗衣机的时间按从小到大排序

然后挨个按结束时间贪心

烘干机的贪心就是尽量把后洗完的配给时间更短的烘干机

使等待的时间最小化

等待的时间可以重叠，但是同一台烘干机的烘干时间是不能重叠的

如果一台烘干机要工作两次，那么尽量让这两次中间不等待，所以：

此时的t[i]更新为总时间

下面会解释用同一台烘干机的情况，不同烘干机互不影响，直接贪心就好

代码

  1 /*****************************
  2 User:Mandy.H.Y
  3 Language:c++
  4 Problem:laundry
  5 *****************************/
  6 //君之清极，当宿花丛，睡云端，不知寒 
  7 #include<bits/stdc++.h>
  8 #define Max(x,y) ((x) > (y) ? (x) : (y))
  9 #define Min(x,y) ((x) < (y) ? (x) : (y))
 10 
 11 using namespace std;
 12 
 13 const int maxn = 1e6 + 5;
 14 
 15 int l,n,m;
 16 long long w[maxn],d[maxn],ans;
 17 long long t[maxn],t2[maxn];
 18 long long cntw[maxn],cntd[maxn];
 19 
 20 struct Node{
 21     long long t,id;
 22     Node(long long _t=0,long long _id=0):t(_t),id(_id){}
 23     bool operator <(const Node &a)const {
 24         return t > a.t;
 25     }
 26 };
 27 
 28 priority_queue<Node>q1,q2,q3;
 29 
 30 template<class T>inline void read(T &x){
 31     x = 0;bool flag = 0;char ch = getchar();
 32     while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
 33     while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
 34     if(flag) x = -x;
 35 }
 36 
 37 template<class T>void putch(const T x){
 38     if(x > 9) putch(x / 10);
 39     putchar(x % 10 | 48);
 40 }
 41 
 42 template<class T>void put(const T x){
 43     if(x < 0) putchar('-'),putch(-x);
 44     else putch(x);
 45 }
 46 
 47 void file(){
 48     freopen("laundry.in","r",stdin);
 49     freopen("laundry.out","w",stdout);
 50 }
 51 
 52 void readdata(){
 53     read(l);read(n);read(m);
 54     for(int i = 1;i <= n; ++ i) read(w[i]); 
 55     for(int i = 1;i <= m; ++ i) read(d[i]); 
 56     sort(w + 1,w + n + 1);
 57     sort(d + 1,d + m + 1);
 58 
 59 }
 60 
 61 void work1(){
 62     put(w[1] + d[1]);
 63 }
 64 
 65 void work(){
 66     long long cn=1,cm=1;
 67     q1.push(Node(w[1],cn));
 68     for(int i = 1;i <= l; ++ i){
 69         
 70         Node x = q1.top();
 71         q1.pop();
 72         t[i] = x.t;
 73         q1.push(Node(x.t + w[x.id],x.id));
 74         if(x.id == cn){
 75             cn++;
 76             if(cn <= n)q1.push(Node(w[cn],cn)); 
 77         } 
 78     }
 79     q2.push(Node(d[cm],cm));
 80     for(int i = l;i >= 1; -- i){
 81         Node x = q2.top();
 82         q2.pop();
 83         if(x.id == cm) {    
 84             cm++;
 85             if(cm <= m)q2.push(Node(d[cm],cm));
 86         }
 87         t[i] += x.t;
 88         //这里的t[i]不一定就是真实的洗衣时间，但对答案无影响 
 89         //最小化等待时间 
 90         x.t += d[x.id];
 91         q2.push(x);
 92         ans = max(ans,t[i]); 
 93     }
 94     put(ans);
 95 }
 96 
 97 int main(){
 98 //    file();
 99     readdata();
100     if(l == 1) work1();
101     else work();
102     return 0;
103 }

View Code