题目描述
高二数学《绿色通道》总共有n道题目要抄,编号1 ldots n1…n,抄第i题要花a_iai分钟。小Y决定只用不超过t分钟抄这个,因此必然有空着的题。每道题要么不写,要么抄完,不能写一半。下标连续的一些空题称为一个空题段,它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒,最长的空题段越长,马老师越生气。
现在,小Y想知道他在这t分钟内写哪些题,才能够尽量减轻马老师的怒火。由于小Y很聪明,你只要告诉他最长的空题段至少有多长就可以了,不需输出方案。
现在,小Y想知道他在这t分钟内写哪些题,才能够尽量减轻马老师的怒火。由于小Y很聪明,你只要告诉他最长的空题段至少有多长就可以了,不需输出方案。
输入描述:
第一行为两个整数n,t。
第二行为n个整数,依次为a1,a2,…,an。
输出描述:
输出一个整数,表示最长的空题段至少有多长。
输入
17 11 6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5
输出
3
说明
#include<bits/stdc++.h> using namespace std; const int N = 5e4 + 7; int a[N], dp[N], q[N], n, t; bool check(int m) { memset(dp, 0, sizeof(dp)); int l = 0, r = 0; for (int i = 1; i <= n; i++) { dp[i] = dp[q[l]] + a[i]; while (l <= r && i - q[l] > m) l++; while (l <= r && dp[q[r]] >= dp[i]) r--; q[++r] = i; } for (int i = n - m + 1; i <= n; i++) { if (dp[i] <= t) return true; } return false; } int main() { cin >> n >> t; for (int i = 1; i <= n; i++) cin >> a[i]; int l = 0, r = n, ans; while (l <= r) { int m = (l + r) >> 1; if (check(m)) r = m - 1, ans = m; else l = m + 1; } cout << ans << endl; return 0; }
原文链接: https://www.cnblogs.com/HighLights/p/13331015.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/367598
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!