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.
InputThe 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.
OutputPrint one integer — the minimum number of days in which Vasiliy can pass all exams. If it is impossible, print -1.
Examplesinput7 2output
0 1 0 2 1 0 2
2 1
5input
10 3output
0 0 1 2 3 0 2 0 1 2
1 1 4
9input
5 1output
1 1 1 1 1
5
-1Note
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.
Source
Codeforces Round #377 (Div. 2)
My Solution
二分+贪心 or 纯贪心水过
/*!!!!!!
1、纯贪心水过，事实上并不对
比赛的时候是纯贪心水过了，后来经过同学和热心读者们的提醒，发现纯贪心是水过去的，事实上并不对，抱歉
首先a[maxn] 进行排序，
然后扫一遍d[maxn]， 对于每次 d[i] == 0，则cnt++;
d[i] >= 0， 则如果 cnt >= a[ptr] 则 cnt -= a[ptr]， ptr++;
否则 cnt++;
这里要注意 He can mix the order of preparation for exams in any way. 这句话
所以优先使用小的a[i]，因为当cnt足够的时候， 大的a[i]能用的时候，小的a[i]也能用，而如果只能小的a[i]用的时候 大的a[i]却不能用，
要尽可能少的天数，所以当遇到d[i] > 0 时就先把小的用掉，因为这个时候大的可能不能用， 尽可能把当前遇到的d[i] > 0 的 i用掉( 用来考试),
//因为d[i] == 0 只能复习，而d[i] > 0，可以2种用途，优先把d[i]用来考试，则对后面可以安排的更自如。
复杂度 O(n)
*/
2、二分+贪心
二分右端点，然后check [0, x) 能不能满足条件，然后可以则 r = x, 否则l = x;
关于check()函数，从右端点往左扫一遍，只留下最靠右的相同d[j]值(把这些处理后的数据放到一个新的数组b[nmaxn]里)，然后从左往右贪/*贪心的策略就是"1、纯贪心水过的策略"*/
最后的r就是答案了，
当 r == l 是 可能是没有答案也可能答案为n，所以对于这种情况再check(n)一次
复杂度 O(nlogn)
1、纯贪心水过，事实上并不对
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;
LL d[maxn], a[maxn];
int main()
{
#ifdef LOCAL
freopen("d.txt", "r", stdin);
//freopen("d.out", "w", stdout);
int T = 6;
while(T--){
#endif // LOCAL
ios::sync_with_stdio(false); cin.tie(0);
LL n, m;
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> d[i];
}
for(int i = 0; i < m; i++){
cin >> a[i];
}
sort(a, a + m);
int cnt = 0, ptr = 0, ans = 0;
for(int i = 0; i < n; i++){
if(ptr == m) {ans = i; break;}
if(d[i] == 0) cnt++;
else{
if(cnt < a[ptr]){
cnt++;
}
else{
cnt -= a[ptr];
ptr++;
}
}
}
if(ptr != m) cout << -1 << endl;
else{
if(ans == 0) cout << n << endl; //
else cout << ans << endl;
}
#ifdef LOCAL
cout << endl;
}
#endif // LOCAL
return 0;
}
2、二分+贪心
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;
int d[maxn], a[maxn], b[maxn], n, m;
map<int, bool> mp;
inline bool check(int x)
{
mp.clear();
for(int i = x - 1; i >= 0; i--){
if(mp[a[i]]) b[i] = 0;
else{
b[i] = a[i];
mp[a[i]] = true;
}
}
int cnt = 0, ptr = 0, ans = 0;
for(int i = 0; i < x; i++){
if(ptr == m) {ans = i; break;}
if(d[i] == 0) cnt++;
else{
if(cnt < a[ptr]){
cnt++;
}
else{
cnt -= a[ptr];
ptr++;
}
}
}
if(ptr != m) return false;
else{
return true;
}
}
int main()
{
#ifdef LOCAL
freopen("d.txt", "r", stdin);
//freopen("d.out", "w", stdout);
int T = 6;
while(T--){
#endif // LOCAL
ios::sync_with_stdio(false); cin.tie(0);
//int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> d[i];
}
for(int i = 0; i < m; i++){
cin >> a[i];
}
sort(a, a + m);
int l = 0, r = n, x;
while(l + 1 < r){
x = (l + r) >> 1;
if(check(x)) r = x;
else l = x;
}
if(r == n){
if(check(n)) cout << n <<endl;
else cout << -1 << endl;
}
else cout << r << endl;
#ifdef LOCAL
cout << endl;
}
#endif // LOCAL
return 0;
}
Thank you!
------from ProLights