題意：

給出一串?dāng)?shù)字，代表了第i天能夠進(jìn)行哪場(chǎng)考試，如果為0就不能考試，每天只能考一場(chǎng)。一共要考m場(chǎng)試，每門科目要a[i]的復(fù)習(xí)時(shí)間，所以問(wèn)最快第幾天能夠考完所有科目。

要點(diǎn)：

一開始我覺(jué)得BFS可以做，后來(lái)發(fā)現(xiàn)狀態(tài)量沒(méi)法表示，網(wǎng)上看了一下，原來(lái)可以用二分做，因?yàn)楫?dāng)?shù)趇天時(shí)考科目d[i]時(shí)，你最多可以有i-1天復(fù)習(xí)，然后如果這天考試了，再往前進(jìn)行狀態(tài)轉(zhuǎn)移。這題還是有點(diǎn)難度的，方法比較巧妙，有必要記錄一下。

#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;//注意這里，如果前面有考試日，本身這天不能復(fù)習(xí)，所以要-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; }

轉(zhuǎn)載于:https://www.cnblogs.com/seasonal/p/10343670.html

總結(jié)

以上是生活随笔為你收集整理的codeforces732D Exams(二分)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。