【双指针优化DP】CF985E

柔情只为你懂 2024-03-22 22:02 107阅读 0赞

[Problem - 985E - Codeforces][]

题意：

![ee26455e53004306a721690846e8f85a.png][]

![70bc5bc57bc344d7970b549e1e6c872e.png][]

思路：

首先肯定需要排个序，然后分段DP

但是平常写的分段DP都是n^2的，这里的可以发现单调性，因此考虑双指针转移

这里两个指针都代表两个段的右端点

这里双指针的合理性很明显

想象指针为了满足位置相距K，先j=max(j,i+K)了

然后还得满足极差<=D，因此需要移动几个距离

合理性重点在于当另一个指针i往前移动一格时，j有没有必要回溯

答案是没有必要，因为回溯会导致极差更小，而相距距离也更小了

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=5e5+10;
    
    int N,K,D;
    int a[mxn],dp[mxn];
    
    void solve(){
    	cin>>N>>K>>D;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	sort(a+1,a+1+N);
    	int j=1;
    	dp[0]=1;
    	for(int i=0;i<=N;i++){
    		if(dp[i]){
    			j=max(j,i+K);
    			while(j<=N&&a[j]-a[i+1]<=D) dp[j]=1,j++;
    		}
    	}
    	if(dp[N]==1) cout<<"YES"<<'\n';
    	else cout<<"NO"<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - 985E - Codeforces]: https://codeforces.com/problemset/problem/985/E
[ee26455e53004306a721690846e8f85a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/9bd199479b704173a093992258564e46.png
[70bc5bc57bc344d7970b549e1e6c872e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/ef9b38c6098f4ea1bebbf1dd72651449.png

发表评论取消回复

表情：

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

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

相关阅读

相关双指针技术

双指针技术重要性：非常高数据结构和算法的第2天注意：每天都会有新的双指针技术问题和解决方案加入。因此，请保持每天检查这个帖子。让

深碍√TFBOYSˉ_/ 2024年04月01日 11:32/ 0 赞/ 82 阅读

相关双指针专题

双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。在数组的区间问题上，暴力算法的时间复

左手的ㄟ右手/ 2024年03月27日 18:03/ 0 赞/ 117 阅读

相关【双指针优化DP】CF985E

[Problem - 985E - Codeforces][] 题意： ![ee26455e53004306a721690846e8f85a.png][] ![70bc5

柔情只为你懂/ 2024年03月22日 22:02/ 0 赞/ 108 阅读

相关【二维偏序+双指针】ABC245 E

[E - Wrapping Chocolate (atcoder.jp)][E - Wrapping Chocolate _atcoder.jp] 题意： ![761342

女爷i/ 2024年03月17日 14:41/ 0 赞/ 90 阅读

相关算法——双指针

一、背景知识 > 双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。 >

- 日理万妓/ 2024年02月18日 13:03/ 0 赞/ 82 阅读

相关 [leetcode 双指针]

1. 三数之和 M :::details > 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c =

超、凢脫俗/ 2024年02月05日 12:49/ 0 赞/ 31 阅读

相关双指针

- (void)viewDidLoad { [super viewDidLoad]; //定义的指针叫做双指针

港控/mmm°/ 2023年10月17日 05:23/ 0 赞/ 27 阅读

相关 LeetCode——双指针

双指针双指针主要用来遍历数组，两个指针指向不同的元素，从而协同完成任务。 -------------------- 目录 1. 有序数组的 Two Sum

忘是亡心i/ 2023年06月15日 04:57/ 0 赞/ 35 阅读

相关 leetcode——双指针

leetcode——双指针 1. 两数之和Ⅱ-输入有序数组（167） 2.合并两个有序数组（88） 3.快慢

分手后的思念是犯贱/ 2022年10月31日 00:43/ 0 赞/ 222 阅读

相关 06双指针

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ2Flc2FyQ2hhbmc_size_9_c

小咪咪/ 2022年09月15日 05:46/ 0 赞/ 198 阅读