题意:
给出一串数字,代表了第i天能够进行哪场考试,如果为0就不能考试,每天只能考一场。一共要考m场试,每门科目要a[i]的复习时间,所以问最快第几天能够考完所有科目。
要点:
一开始我觉得BFS可以做,后来发现状态量没法表示,网上看了一下,原来可以用二分做,因为当第i天时考科目d[i]时,你最多可以有i-1天复习,然后如果这天考试了,再往前进行状态转移。这题还是有点难度的,方法比较巧妙,有必要记录一下。
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n, m;
int d[100050], a[100050];
bool vis[100050];bool check(int x)
{memset(vis, false, sizeof(vis));int cur = x - 1;for (int i = x; i >= 1; i--){cur = min(cur, i - 1);if (d[i] && !vis[d[i]] && a[d[i]] <= cur){vis[d[i]] = true;cur = cur - a[d[i]]-1;//注意这里,如果前面有考试日,本身这天不能复习,所以要-1} }for (int j = 1; j <= m; j++)if (!vis[j])return false;return true;
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", &d[i]);for (int i = 1; i <= m; i++)scanf("%d", &a[i]);int left = 1, right = n, mid,ans=-1;while(left <= right){mid = (left + right) / 2;if (check(mid)){right = mid-1;ans = mid;}else{left = mid + 1;}}printf("%d\n", ans);return 0;
}