牛客练习赛16 B 漂亮的树【哈希hash/思维】
2024-08-29 10:33:54
链接:https://www.nowcoder.com/acm/contest/84/B
来源:牛客网
题目描述
街上有n棵树,标号为1...n,第i棵树的高度为ai。
定义这n棵树是漂亮的,当且仅当
1. 对于所有的i,ai=an-i+1;
2. 对于1 <= i < n / 2 (不是整除),ai + 1= ai + 1;
比如说 “2 3 4 5 5 4 3 2”和“1 2 3 2 1”是漂亮的而“1 3 3 1”和“1 2 3 1”不是。
现在请问最少修改几棵树的高度(可以变大也可以变小),使得这些树是漂亮的。
输入描述:
第一行一个整数n表示树的数量( 1 <= n <= 100,000)。
第二行n个整数表示树的高度( 1 <= ai <= 100,000)。
输出描述:
输出一个整数表示最少修改树的高度的数目。
示例1
输入
3
2 2 2
输出
1
示例2
输入
4
1 2 2 1
输出
0
【分析】:
我们先考虑
\(\frac{n+1}{2}\)
的数字,由于
$a_i - a_{i-1} = 1$
,所以必须调成差值为1的递增序列。
朴素想法是先确定
$a_1$
的值,对于不同的
$a_1 = k$
我们算有多少个
$a_i = k + i$
找最大的那个。这样就把ai分成几个集合。但是这样枚举k会TLE。
但是这是你会发现,对于在一个集合里的元素
\(a_i-i\)
是相同的。
所以统计一下每个值
\(ai-i\)
的数量。然后找到这些数量的最大值,n-最大值 为答案。
可能出现负数,桶排时下标+mod。
#include<bits/stdc++.h>
using namespace std;
const int N = 1000005;
const int mod = 1e5;
int n;
int a[N];
int cnt[N*2];
/*
最后的数之间的差值是固定的,如1,2,3,2,1 ; 1,2,2,1
原来的数减去最终的数(以a[1]=x为基准),求出现次数最多的数。
以12345...n...54321为基点,看每个位置偏离了多少,然后偏移量出现次数最多的为m,答案就是n-m
*/
int main()
{
while(~scanf("%d",&n))
{
memset(a,0,sizeof(a));
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++)
scanf("%d",a+i);
int mid=(n+1)/2;
for(int i=1;i<=mid;i++)
cnt[a[i]-i+mod]++;
for(int i=mid+1;i<=n;i++)
cnt[a[i]-(n-i+1)+mod]++;
int ans=0;
for(int i=1;i<=mod+mod;i++)
ans=max(ans,cnt[i]);
printf("%d\n",n-ans);
}
}
最新文章
- asp.net中http提交数据所遇到的那些坑
- 使用ar命令删除iOS静态库重复编译的.o文件
- 使用bs4对海投网内容信息进行提取并存入mongodb数据库
- HDU 4630 No Pain No Game 树状数组+离线查询
- Asp.net 后台添加Meta标签方法
- C#读写word
- Sublime Text 3 注册码
- 求助:关于sql如何统计时间的问题
- 记录下项目中常用到的JavaScript/JQuery代码一(大量实例)
- 4月22日MySQL学习
- Python数据可视化编程实战pdf
- Python 爬虫 某迅漫画 selemiun+plantomJS
- 使用Pandas将多个数据表合一
- μC/OS-II 信号量集
- puppet 和 apache passenger的配置
- 多线程 ThreadLocal
- EAS_BI(扩展报表)
- 算法笔记_191:历届试题 大臣的旅费(Java)
- 【题解】洛谷P1351 [NOIP2014TG] 联合权值(树形结构+DFS)
- C++ Primer 第8章作业
热门文章
- day04_08-while查询所有行
- Windows 下开发.NET Core应用
- Android动态添加和移除布局
- Android事件分发机制详解(2)----分析ViewGruop的事件分发
- 小木乃伊到我家 dijkstra + 链表 + 优先队列
- openssl unicode编译以及VC++2015环境下的问题
- thinkPHP判断是否修改成功
- [codeforces] 526D [51nod] 1554 欧姆诺姆和项链
- python注解(装饰器)的用法
- 搭建自己的YUM源HTTP服务器