忻州网站建设公司,企业网站设计文档,seo网站设计费用,专业网站发展趋势题干#xff1a;
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个长度为N的数组A1, A2, ... AN#xff0c;请你判断其中有几个元素Ai按如下跳跃规则能跳到最后一个元素AN。
假设你当前位于Ai#xff0c;跳跃的规则是#xff1a;
如果这一步是第奇…题干
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个长度为N的数组A1, A2, ... AN请你判断其中有几个元素Ai按如下跳跃规则能跳到最后一个元素AN。
假设你当前位于Ai跳跃的规则是
如果这一步是第奇数次跳跃(从1开始计数)可以跳到Ai之后(Ai1 .. AN)比Ai大的最小的元素
如果这一步是第偶数次跳跃可以跳到Ai之后(Ai1 .. AN)比Ai小的最大的元素
如果有多个满足条件的元素则跳到其中下标最小的元素。
如果没有满足条件的元素则在当前的Ai停下来。
例如对于A [3, 2, 4, 1, 5]如果从3开始第一步从3跳到4第二步从4跳到1第三步从1跳到5。
输入
第一行包含一个整数N。
第二行包含N个整数A1, A2, ... AN。
对于30%的数据1 N 100
对于60%的数据1 N 1000
对于100%的数据1 N 100000 1 Ai 1000000
输出
一个整数代表答案
样例输入
5
3 4 1 2 5
样例输出
4
解题报告 先用set倒着扫一遍数组顺便预处理出距离最近的比他大的最小的数的下标和距离最近的比他小的最大的数的下标这一步可以用单调栈O(n)实现但是因为时间允许于是set好写一些。然后dp代表从编号i开始的第偶数/奇数步能不能到达最后。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#includecctype
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e6 5;
setint ss;
bool dp[MAX][2];
int big[MAX],small[MAX],pos[MAX],a[MAX];//预处理出后面第一个比他大的和第一个比他小的
int main() {int n;cinn;for(int i 1; in; i) scanf(%d,ai);for(int i n; i1; i--) {if(ss.count(a[i])) pos[a[i]] i;else ss.insert(a[i]),pos[a[i]] i;auto it ss.upper_bound(a[i]);if(it ! ss.end()) big[i] pos[*it];else big[i] -1;it ss.lower_bound(a[i]);if(it ss.begin()) small[i] -1;else {--it;small[i] pos[*it];}}
// for(int i 1; in; i ) {
// printf(i: %d : %d %d\n,i,big[i],small[i]);
// }dp[n][0] 1,dp[n][1] 1;for(int i n-1; i1; i--) {if(big[i] ! -1) dp[i][1] dp[big[i]][0];if(small[i] ! -1) dp[i][0] dp[small[i]][1];}int ans 0;for(int i 1; in; i) {if(dp[i][1]) ans;}printf(%d\n,ans);return 0 ;}
注意因为题中的大于和小于都是严格大于和严格小于所以判断大于必须用upper否则可能set中已经有一个a[i]了你再lower就肯定不对了。
同样的也可以用map实现
#include bits/stdc.h
using namespace std;
const int N 1e555;
int dp[N][2];
int a[N];
int main()
{int n;cinn;for(int i1;in;i)cina[i];mapint,int mp;mapint,int ::iterator it;mp[a[n]] n;dp[n][1] 1;dp[n][0] 1;for(int in-1;i0;--i){it mp.lower_bound(a[i]);if(itmp.end()||itmp.begin()) dp[i][0] 0;else dp[i][0] dp[(--it)-second][1];it mp.upper_bound(a[i]);if(itmp.end()) dp[i][1] 0;else dp[i][1] dp[it-second][0];mp[a[i]]i;}int ans 0;for(int i1;in;i){if(dp[i][1]) ans;}coutans;return 0;
}