Advertisement
Patrickmeme

JOb Scheduling

Jun 11th, 2023
652
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. struct vc{
  6.     int a,ind;
  7. }v[10000];
  8.  
  9. bool cmp(vc a,vc b){
  10.     if(a.a<b.a)
  11.         return 1;
  12.     else
  13.         return 0;
  14. }
  15.  
  16. int n,m;
  17.  
  18. bool verf(int mij){
  19.     int z,i;
  20.     z=mij-1;i=1;
  21.     while(z<m-1 && i<=n){
  22.         if(i>v[z].a)
  23.             break;
  24.         i++;
  25.         z=min(z+mij,m-1);
  26.     }
  27.     if(z<m-1 && i<=n)
  28.         return 0;
  29.     else
  30.         return 1;
  31. }
  32.  
  33. int main()
  34. {
  35.     int st,dr,mij,d,rasp,i,vf,poz,j;
  36.     cin>>n>>d>>m;
  37.     for(i=0;i<m;i++){
  38.         cin>>v[i].a;
  39.         v[i].ind=i+1;
  40.         v[i].a+=d;
  41.     }
  42.     sort(v,v+m,cmp);
  43.     st=1;dr=1000000;rasp=mij=0;
  44.     while(st<=dr){
  45.         mij=(st+dr)/2;
  46.         vf=verf(mij);
  47.         if(vf==1){
  48.             rasp=mij;
  49.             dr=mij-1;
  50.         }else{
  51.             st=mij+1;
  52.         }
  53.     }
  54.     cout<<rasp<<"\n";
  55.     poz=0;
  56.     for(i=0;i<n;i++){
  57.         for(j=0;j<rasp && poz<m;j++){
  58.             cout<<v[poz].ind<<" ";
  59.             poz++;
  60.         }
  61.         cout<<"0\n";
  62.     }
  63.  
  64.     return 0;
  65. }
  66.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement