1 second
256 megabytes
standard input
standard output
Vasiliy has an exam period which will continue for n days. He has to pass exams on m subjects. Subjects are numbered from 1 to m.
About every day we know exam for which one of m subjects can be passed on that day. Perhaps, some day you can't pass any exam. It is not allowed to pass more than one exam on any day.
On each day Vasiliy can either pass the exam of that day (it takes the whole day) or prepare all day for some exam or have a rest.
About each subject Vasiliy know a number ai — the number of days he should prepare to pass the exam number i. Vasiliy can switch subjects while preparing for exams, it is not necessary to prepare continuously during ai days for the exam number i. He can mix the order of preparation for exams in any way.
Your task is to determine the minimum number of days in which Vasiliy can pass all exams, or determine that it is impossible. Each exam should be passed exactly one time.
The first line contains two integers n and m (1 ≤ n, m ≤ 105) — the number of days in the exam period and the number of subjects.
The second line contains n integers d1, d2, ..., dn (0 ≤ di ≤ m), where di is the number of subject, the exam of which can be passed on the day number i. If di equals 0, it is not allowed to pass any exams on the day number i.
The third line contains m positive integers a1, a2, ..., am (1 ≤ ai ≤ 105), where ai is the number of days that are needed to prepare before passing the exam on the subject i.
Print one integer — the minimum number of days in which Vasiliy can pass all exams. If it is impossible, print -1.
7 2
0 1 0 2 1 0 2
2 1
5
10 3
0 0 1 2 3 0 2 0 1 2
1 1 4
9
5 1
1 1 1 1 1
5
-1
In the first example Vasiliy can behave as follows. On the first and the second day he can prepare for the exam number 1 and pass it on the fifth day, prepare for the exam number 2 on the third day and pass it on the fourth day.
In the second example Vasiliy should prepare for the exam number 3 during the first four days and pass it on the fifth day. Then on the sixth day he should prepare for the exam number 2 and then pass it on the seventh day. After that he needs to prepare for the exam number 1 on the eighth day and pass it on the ninth day.
In the third example Vasiliy can't pass the only exam because he hasn't anough time to prepare for it.
思路就是二分加贪心，还是不会做，找了大神的代码，仔细研读了一下，受益匪浅，做了一点注释，就发上方便以后自己查阅
错误地地方请指正
#include <bits/stdc++.h>
using namespace std;
const int Maxn=100100;
int A[Maxn];
int B[Maxn];
vector<int>v[Maxn];
int N,M; bool f(int i){
vector<pair<int,int> >t;//pair里存的是点的位置，和值
for(int j = 1; j <= M; j++){
int p = upper_bound(v[j].begin(),v[j].end(),i) - v[j].begin() -1;//寻找该点里的最大值，就是队列v[j]队列里面最大值的位置，用来判断前面的天数是否可以够他复习
if( p == -1 ){
return false;//如果找不到，那么这个mid的值不满足
}
t.push_back( {v[j][p],B[j]} );//放进一个新的队列
}
sort(t.begin(),t.end());//排序的目的是按照点的位置排序，目的是贪心原理
int k = -1;//k的意思是到这次考试时候，化肥这次考试前面（队列顺序）考试复习需要的总天数
for(auto i:t){//遍历队列中的所有值，
if( i.second+k >= i.first ){//如果总天数+这次需要的天数，比安排那天考试的天数（即该点顺序）大，就返回假，否则累加
return false;
}else{
k += i.second+1;
}
}
return true;
} int main(){
cin >> N >> M;
for(int i = 0; i < N; i++){
cin >> A[i];//输入该点的值
v[A[i]].push_back(i);//存放该值的位置
}
for(int i = 1; i <= M; i++){
cin >> B[i];//输入要复习多少天
}
int l = -1;
int r = N + 1;
while( l < r-1 ){//二分，直到找到一个区间（1,mid）满足条件
int mid = (l+r)>>1;
if( f(mid) ){
r = mid;
}else{
l = mid;
}
}
if( r != N+1 ){
cout << r+1 << endl;
}else{
cout << -1 << endl;
}
}