洛谷P3929 SAC E#1 - 一道神题 Sequence1【枚举】
题目描述
小强很喜欢数列。有一天,他心血来潮,写下了一个数列。
阿米巴也很喜欢数列。但是他只喜欢其中一种:波动数列。
一个长度为n的波动数列满足对于任何i(1 <= i < n),均有:
a[2i-1] <= a[2i] 且 a[2i] >= a[2i+1](若存在) 或者
a[2i-1] >= a[2i] 且 a[2i] <= a[2i+1](若存在)
阿米巴把他的喜好告诉了小强。小强便打算稍作修改,以让这个数列成为波动数列。他想知道,能否通过仅修改一个数(或不修改),使得原数列变成波动数列。
输入输出格式
输入格式:
输入包含多组数据。
每组数据包含两行。
第一行一个整数n表示数列的长度。
接下来一行,n个整数,表示一个数列。
输出格式:
对于每一组输入,输出一行Yes或No,含义如题目所示。
输入输出样例
5
1 2 3 2 1
5
1 2 3 4 5
Yes
No
说明
对于30%的数据,n <= 10
对于另外30%的数据,m <= 1000
对于100%的数据,n <= 10^5,m <= 10^9
其中m = max|a[i]|(数列中绝对值的最大值)
【分析】:
如果给定一个序列,可以很容易的在 O(n) 时间内判断该序 列是否为波动序列。 首先判断该序列是否为波动序列,如果是,则直接输 出”Yes“。 否则,枚举修改哪一个数。 可以发现如一个数要被修改,则将其改为 ∞ 或 −∞ 一定不 会比修改为别的数不优。 所以将其修改为 ∞ 或 −∞ 后再次判断。 总复杂度 O(n^2)。
AC: 由于波动序列本质上只有 2 种,所以对于每一种波动序列, 求出将原序列变为这种波动序列最少需要修改几次。
如果两个值的较小值不大于 1,则输出”Yes“,否则输出”No“。
问题变为求原序列变为某种波动序列需要的最小修改次数。 从前向后扫,如果遇到某个元素不满足要求,则将该元素修 改为 ∞ 和 −∞ 中满足要求的那个,并将计数器加一。
最后计数器的值就是修改需要的最小次数。 总复杂度 O(n)。
【代码】:
#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 100010 using namespace std; int a[maxn];
int n; bool judge(bool dir)// 首先判断该序列是否为波动序列,如果是,则直接输 出”Yes“。 否则,枚举修改哪一个数。
{
int cnt = ;
for (int i = ; i <= n; i++, dir = !dir)
if (a[i] != a[i-] && (a[i] > a[i-]) != dir)
if (++cnt > )
return false;//从前向后扫,如果遇到某个元素不满足要求,则将该元素修 改为 ∞ 和 −∞ 中满足要求的那个,并将计数器加一。
else
{
i++;
dir = !dir;
}
return true;
} int main()
{
while (scanf("%d", &n) >= )
{
for (int i = ; i <= n; i++)
scanf("%d", &a[i]); if (n <= )
printf("Yes\n");
else
printf(judge() || judge() ? "Yes\n" : "No\n");
}
//如果两个值的较小值不大于 1,则输出”Yes“,否则输出”No“。
return ;
}
最新文章
- MacOS中使用QT开发iOS应用
- iOS开发UI篇—iPad开发中得modal介绍
- iOS设置UISearchBar光标的颜色
- 泛函编程(7)-数据结构-List-折叠算法
- asp.net网站 提示Ambiguous match found
- C#日期格式精确到毫秒以及上下午
- 延期(deferred)的承诺(promise) — jq异步编程浅析
- 【转】怎样创建一个Xcode插件(Part 2)
- poj 1014多重背包
- 微信支付之02------整个微信支付功能----------Java实现
- Ansible-Zabbix-基础agent批量装机
- Curl追踪请求延时问题
- pandas的to_csv()使用细节和一些参数
- 10行代码解析krc歌词文件
- 【机器学习】K-means聚类算法与EM算法
- Java第十次作业--多线程
- JSP分页之结合Bootstrap分页插件进行简单分页
- Spring Boot - 杂项
- nginx里配置跨域
- pdb 源码索引符号服务器创建过程
热门文章
- 【bzoj2705】[SDOI2012]Longge的问题 欧拉函数
- POJ——2449 Remmarguts&#39; Date
- BZOJ5323 [Jxoi2018]游戏 【数论/数学】
- [POI2006] OKR-period of words
- centos安装net-speeder
- sqrti128
- bzoj 4237 稻草人 CDQ
- Prepare and Deploy Windows Server 2016 Active Directory Federation Services
- jquery学习之事件委派
- Idea工具点滴积累