首页 > 代码库 > Codeforces 497C Distributing Parts set+贪心

Codeforces 497C Distributing Parts set+贪心

给定n个任务

下面[l, r]是n个任务需要占用的时间。

m个人

下面是m个人的空闲时间以及这个人至多能做的任务个数(一个人同一时刻只能做一个任务,即人是单线程的)

[l, r] num

问:

若任务不能被全部完成则输出NO

否则输出YES

输出每个任务是谁完成的。

思路:

把人和任务放一起按右端点排序。

若遇到了任务则把任务的左端点放到set里。

若遇到了人,则把set中>=人的左端点的 num个数删掉。

java:

[java] view plaincopy技术分享技术分享
  1. import java.util.ArrayList;  
  2. import java.util.Arrays;  
  3. import java.util.Collections;  
  4. import java.util.HashSet;  
  5. import java.util.Iterator;  
  6. import java.util.List;  
  7. import java.util.Scanner;  
  8. import java.util.Set;  
  9. import java.util.TreeSet;  
  10. public class Main {  
  11.     static int N = 200050;  
  12.     class Edge implements Comparable<Edge>{  
  13.         long id, l;  
  14.         public int compareTo(Edge o){  
  15.             if(l != o.l)return Long.compare(l, o.l);  
  16.             return Long.compare(id, o.id);  
  17.         }  
  18.     }  
  19.     Edge edge(long a, long b){  
  20.         Edge tmp = new Edge();  
  21.         tmp.id = a; tmp.l = b;  
  22.         return tmp;  
  23.     }  
  24.     class Node implements Comparable<Node>{  
  25.         long l, r, id, num, op;  
  26.     /*  public Node(long a, long b, long c, long d, long e){ 
  27.             l = a; r = b; c = id; d = num; e = op; 
  28.         }/**/  
  29.         public int compareTo(Node o){  
  30.             if(r != o.r)  
  31.                 return Long.compare(r, o.r);  
  32.             return Long.compare(op, o.op);  
  33.         }  
  34.     }  
  35.     Node cr(long a, long b, long c, long d, long e){  
  36.         Node tmp = new Node();  
  37.         tmp.l = a; tmp.r = b; tmp.id = c; tmp.num = d; tmp.op = e;  
  38.         return tmp;  
  39.     }  
  40.     int[] b = new int[N], ans = new int[N];  
  41.     ArrayList<Node> a = new ArrayList<>();  
  42.     int n, m;  
  43.     void init(){  
  44.         n = cin.nextInt();  
  45.         long l, r, num;  
  46.         for(int i = 1; i <= n; i++)  
  47.         {  
  48.             l = cin.nextLong(); r = cin.nextLong();  
  49.             a.add(cr(l, r, (long)i, 0L, 0L));  
  50.         }  
  51.         m = cin.nextInt();  
  52.         for(int i = 1; i <= m; i++)  
  53.         {  
  54.             l = cin.nextLong(); r = cin.nextLong(); num = cin.nextLong();  
  55.             a.add(cr(l, r, (long)i, num, 1L));            
  56.         }  
  57.         Collections.sort(a);  
  58.     }  
  59.     TreeSet set = new TreeSet();  
  60.     Iterator p;  
  61.     public void work(){  
  62.         init();  
  63.         set.clear();  
  64.         set.add(edge(-1,0));  
  65.         int siz = 0;  
  66.         for(int i = 0; i < a.size(); i++)  
  67.         {  
  68.             if(a.get(i).op == 1){  
  69.                 while(set.size()>0 && a.get(i).num-->0){  
  70.                     Edge E = (Edge) set.ceiling(edge(0L, a.get(i).l));  
  71.                     if(E==null)break;  
  72.                     siz++;  
  73.                     ans[(int)E.id] = (int)a.get(i).id;   
  74.                     set.remove(E);  
  75.                 }  
  76.             }  
  77.             else   
  78.                 set.add(edge(a.get(i).id, a.get(i).l));  
  79.         }  
  80.         if(siz == n){  
  81.             System.out.println("YES");  
  82.             for(int i = 1; i <= n; i++)  
  83.                 System.out.print(ans[i]+" ");  
  84.         }  
  85.         else System.out.println("NO");  
  86.     }  
  87.     Main() {    
  88.         cin = new Scanner(System.in);    
  89.     }    
  90.     public static void main(String[] args) {  
  91.         Main e = new Main();    
  92.         e.work();  
  93.     }  
  94.     public Scanner cin;  
  95. }  


c:

[cpp] view plaincopy技术分享技术分享
    1. #include <bits/stdc++.h>  
    2. template <class T>  
    3. inline bool rd(T &ret) {  
    4.     char c; int sgn;  
    5.     if(c=getchar(),c==EOF) return 0;  
    6.     while(c!=‘-‘&&(c<‘0‘||c>‘9‘)) c=getchar();  
    7.     sgn=(c==‘-‘)?-1:1;  
    8.     ret=(c==‘-‘)?0:(c-‘0‘);  
    9.     while(c=getchar(),c>=‘0‘&&c<=‘9‘) ret=ret*10+(c-‘0‘);  
    10.     ret*=sgn;  
    11.     return 1;  
    12. }  
    13. template <class T>  
    14. inline void pt(T x) {  
    15.     if (x <0) {  
    16.         putchar(‘-‘);  
    17.         x = -x;  
    18.     }  
    19.     if(x>9) pt(x/10);  
    20.     putchar(x%10+‘0‘);  
    21. }  
    22. using namespace std;  
    23. typedef long long ll;  
    24. #define int ll  
    25. const int N = 200050;  
    26. int n, m;  
    27. struct node{  
    28.     int op, l, r, num, id;  
    29. }a[N*2];  
    30. bool cmp(node x, node y){  
    31.     if(x.r != y.r)  
    32.         return x.r<y.r;  
    33.     if(x.op!=y.op)  
    34.         return x.op<y.op;  
    35. }  
    36. int top, b[N];  
    37. void input(){  
    38.     top = 0;  
    39.     for(int i = 1; i <= n; i++){  
    40.         rd(a[top].l); rd(a[top].r);  
    41.         a[top].op = 0;  
    42.         a[top].id = i;  
    43.         top++;  
    44.     }  
    45.     rd(m);  
    46.     for(int i = 1; i <= m; i++){  
    47.         rd(a[top].l); rd(a[top].r); rd(a[top].num);  
    48.         a[top].op = 1;  
    49.         a[top].id = i;  
    50.         top++;  
    51.     }  
    52.     sort(a, a+top, cmp);  
    53. }  
    54. struct Edge{  
    55.     int id, l;  
    56.     bool operator<(const Edge&e)const{  
    57.         if(e.l!=l)return e.l>l;  
    58.         return e.id>id;  
    59.     }  
    60.     Edge(int a=0,int b=0):id(a),l(b){}  
    61. }tmp;  
    62. set<Edge>s;  
    63. set<Edge>::iterator p;  
    64. #undef int  
    65. int main(){  
    66. #define int ll  
    67.     while(cin>>n){  
    68.         input();  
    69.         int ans = 0;  
    70.         s.clear();  
    71.         for(int i = 0; i < top; i++){  
    72.             if(a[i].op){  
    73.                 while(s.size() && a[i].num--)  
    74.                 {  
    75.                     p = s.lower_bound(Edge(0, a[i].l));  
    76.                     if(p == s.end())break;  
    77.                     tmp = *p;  
    78.                     b[tmp.id] = a[i].id;  
    79.                     s.erase(p);  
    80.                     ans++;  
    81.                 }  
    82.             }  
    83.             else {  
    84.                 s.insert(Edge(a[i].id, a[i].l));  
    85.             }  
    86.         }  
    87.         if(ans == n)  
    88.         {  
    89.             puts("YES");  
    90.             for(int i = 1; i <= n; i++){pt(b[i]); putchar(‘ ‘);}  
    91.         }  
    92.         else puts("NO");  
    93.     }  
    94.     return 0;  

Codeforces 497C Distributing Parts set+贪心