P3143 [USACO16OPEN]钻石收藏家Diamond Collector[two-pointers]

╰+攻爆jí腚メ 2021-12-22 15:55 128阅读 0赞

# P3143 \[USACO16OPEN\]钻石收藏家Diamond Collector #

题意要注意一点：有两个陈列架！

如果只有一个陈列架，是很容易的。two-pointers直接从左到右跑一下即可。

如果有两个陈列架，就需要进行答案合并了。做法是这样的：

设两个数组：

1.  \\(pre\\)数组，\\(pre\[i\]\\)表示以\\(\[1,i\]\\)为右端点时区间长度的最大值。
2.  \\(suf\\)数组，\\(suf\[i\]\\)表示以\\(\[i,n\]\\)为左端点时区间长度的最大值。

两个数组分别是前缀最大值和后缀最大值。同样利用一个陈列架的two-pointers的做法。

最后的答案就是\\(max\_\{i=1\}^\{n+1\} pre\[i-1\] + suf\[i\]\\)。这里的\\(i\\)相当于拼接点。

代码：

#include<bits/stdc++.h> using std::cin; using std::cout; using std::endl; #define ll long long const int maxn = 50005; int a[maxn]; int pre[maxn], suf[maxn]; int n, k; void work1() { for(int r = 1, l = 0; r <= n; r++) { while(a[r] - a[l + 1] > k) l++; pre[r] = std::max(pre[r - 1], r - l); } } void work2() { for(int l = n, r = n + 1; l >= 1; l--) { while(a[r - 1] - a[l] > k) r--; suf[l] = std::max(suf[l + 1], r - l); } } int main() { cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> a[i]; } std::sort(a + 1, a + n + 1); work1(); work2(); int ans = 0; for(int i = 1; i <= n + 1; i++) { ans = std::max(ans, pre[i - 1] + suf[i]); } cout << ans << endl; return 0; }

转载于:https://www.cnblogs.com/Garen-Wang/p/10381458.html

发表评论取消回复

表情：

评论列表（有 0 条评论，128人围观）

还没有评论，来说两句吧...

相关阅读

相关 P2910 [USACO08OPEN]Clear And Present Danger S——FLoyd-Warshell算法N^3解题

题目链接[https://www.luogu.com.cn/problem/P2910][https_www.luogu.com.cn_problem_P2910] ![

本是古典何须时尚/ 2023年01月21日 11:19/ 0 赞/ 108 阅读

相关【USACO-2017-OPEN-银组】 Paired Up

Paired Up 题目描述 Farmer John finds that his cows are each easier to milk w

本是古典何须时尚/ 2022年06月11日 04:07/ 0 赞/ 118 阅读

相关 P4377 [USACO18OPEN]Talent Show

这道题可以作为最优比率背包问题的模板题了。好像属于01分数规划。我们这里用二分答案的方法解决。题目要我们求\\(\\frac\{\\sum\{t\}\}\{\\sum\

àì夳堔傛蜴生んèń/ 2021年12月22日 15:56/ 0 赞/ 106 阅读

相关 P3143 [USACO16OPEN]钻石收藏家Diamond Collector[two-pointers]

P3143 \[USACO16OPEN\]钻石收藏家Diamond Collector 题意要注意一点：有两个陈列架！如果只有一个陈列架，是很容易的。two-poin

╰+攻爆jí腚メ/ 2021年12月22日 15:55/ 0 赞/ 129 阅读

相关 P5242 [USACO19FEB]Cow Dating

[题目链接][Link 1] 题意分析首先我们可以得出计算公式 \\\[s\_i=\\prod\_\{k=1\}^i(1-p\_k)\\\] \\\[f\_i

- 日理万妓/ 2021年12月20日 07:33/ 0 赞/ 122 阅读

相关 Java 9 钻石操作符(Diamond Operator)

钻石操作符是在 java 7 中引入的，可以让代码更易读，但它不能用于匿名的内部类。在 java 9 中，它可以与匿名的内部类一起使用，从而提高代码的可读性。考虑以下

逃离我推掉我的手/ 2021年12月03日 12:31/ 0 赞/ 149 阅读

相关 P3009 [USACO11JAN]利润Profits

题目描述 The cows have opened a new business, and Farmer John wants to see how well they

向右看齐/ 2021年11月26日 07:36/ 0 赞/ 190 阅读

相关 [USACO11OPEN]玉米田迷宫Corn Maze

[题面][Link 1] bfs 注意事项 ①鬼畜死循环TLE ②装置不成对 ③本来最优解被传送门的\给盖住了，必须新开一个数组来存 ④步数没有+对，

忘是亡心i/ 2021年11月13日 15:12/ 0 赞/ 197 阅读

相关 [USACO07OPEN]Catch That Cow

题目：洛谷P1588、HDU2717 题目大意：有一个人在点$n$，一头牛在点$k$，人每秒能从$x$移动到点$x+1$、$x-1$、$2x$，牛不会动，求最少多少秒后人能移

川长思鸟来/ 2021年09月29日 14:50/ 0 赞/ 201 阅读

相关 Java 9 钻石操作符(Diamond Operator)

钻石操作符是在 java 7 中引入的，可以让代码更易读，但它不能用于匿名的内部类。在 java 9 中，它可以与匿名的内部类一起使用，从而提高代码的可读性。考虑以...

灰太狼/ 2020年05月23日 18:07/ 0 赞/ 725 阅读