codeforces 732/D 二分

给出考试时间和考试需要准备的时间,问最早考完所有科目的时间

二分答案 NlogN

二分抄神犇的写法 感觉挺舒服的嘻嘻嘻

 #include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+;
int N,M,d[MAXN],w[MAXN],cnt[MAXN];
void read(int &x){
x=;
register char c=getchar();
while(c<||c>)
c=getchar();
for(;c>=&&c<=;c=getchar())
x=(x<<)+(x<<)+c-;
}
bool check(int x)
{
memset(cnt,,sizeof(cnt));
int ans = ,val = ;
for (int i=x; i>=; i--)
if (d[i]&&++cnt[d[i]]==&&w[d[i]]<i-M+ans+)
{
ans++;
val+=w[d[i]];
}
return ans == M && val+M<=x;
}
int main()
{
read(N),read(M);
for (int i=; i<=N; i++)
read(d[i]);
for (int i=; i<=M; i++)
read(w[i]);
int first = ;
int last = N;
int mid;
int best = -;
while (first <= last)
{
mid = (first + last)/;
if (check(mid))
{
last = mid-;
best = mid;
}
else
{
first = mid+;
}
}
printf("%d\n",best);
return ;
}
上一篇:CoFun 1616 数字游戏


下一篇:689D Friends and Subsequences RMQ+二分