题目链接：

题意：

在m天中要考k个课程，

数组a中有m个元素，表示第a[i]表示第i天可以进行哪门考试，若a[i]为0，则表示当天不能参加任何科目的考试，只能预习或者休息；

数组b中有k个元素，b[i]表示科目i需要复习几天才能通过；

问最快需要几天能通过所有考试，如果不能完成所有科目考试，输出-1；

 

思路：

用二分方法直接找满足条件的最小的数，其中数是指当前天是第几天，条件是指当前天以前是否能考完所有科目（包括当前天）;

 

代码：

1 #include 
     
       2 #define MAXN 100000+10 3 using namespace std; 4  5 int a[MAXN], b[MAXN], n, k; 6  7 int gg(int x){  //××××××判断花费x天能否完成所有科目考试，即能否在第x天以前完成所有科目考试； 8     int cnt=0, vis[MAXN]; 9     memset(vis, 0, sizeof(vis));10     for(int i=x; i>=0; i--){11         // cout << cnt << "//" << endl;12         if(!a[i]){13             cnt--;14             cnt=max(cnt, 0);15         }else if(!vis[a[i]]){16             cnt+=b[a[i]-1];17             // cout << cnt << "***" << endl;18             vis[a[i]]=1;19             if(cnt>i){20                 return 0;21             }22         }else if(vis[a[i]]){23             cnt--;24             cnt=max(0, cnt);25         }26     }27     for(int i=1; i<=k; i++){28         if(!vis[i]){29             return 0;30         }31     }32     return 1;33 }34 35 int main(void){36     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);37     cin >> n >> k;38     for(int i=0; i
      
       > a[i];40     }41     for(int i=0; i
       
        > b[i];43     }44     int l=0, r=n;45     while(l
        
         >1;47         // cout << mid << " " << gg(mid) << endl;//****48         if(gg(mid)){49             r=mid;50         }else{51             l=mid+1;52         }53     }54     if(l>=n){55         cout << "-1" << endl;56     }else{57         cout << l+1 << endl;58     }59     return 0;60 }