【C++竞赛 B】yyy的回文数组
2023-09-14 09:03:47 时间
时间限制:1s 内存限制:32MB
问题描述
回文串是一个正读和反读都一样的字符串,比如level或者noon就是回文串。回文数组也是如此,比如[100,200,100]或者[178,256,256,178]就是回文数组,[1,2,3]和[100,200]不是回文数组。
现在yyy有一个数组,他想仅仅通过合并操作将数组转换为回文数组,
合并操作:将数组中相邻两个的数合并为一个数,合并后的数为合并前两个数的和。例如[1,2,3]通过一次合并操作即可变成回文数组[3,3]。
输入描述
第一行一个整数T(1≤T≤10)表示数据组数。
对于每组数据第一行一个整数n(1≤n≤〖10〗^5),表示数组的长度。
第二行n个整数A_1,A_2,…,A_n (1≤A_i≤10000)分别表示数组中的每个数。
输出描述
对于每组数据输出一行:一个整数表示最少的合并次数。
输入样例
1
3
1 2 3
输出样例
1
【题目链接】:
【题解】
用两个指针,哪个指针指的数字小;则那个指针往中间的方向合并(相邻的);
如果数字相同则两个指针都往中间靠;
【完整代码】
#include <bits/stdc++.h>
#define rep1(i,a,b) for (int i = a;i <= b;i++)
using namespace std;
#define pb push_back;
long long num[100005];
int main()
{
//freopen("D:\\rush.txt","r",stdin);
ios::sync_with_stdio(false);
long long t,n;
long long ans;
cin>>t;
while(t--)
{
cin>>n;
ans = 0;
for(int i=1;i<=n;i++)
{
cin>>num[i];
}
int l = 1,r = n;
while(1)
{
if(num[l]<num[r])
{
num[l+1] = num[l]+num[l+1];
l++;
ans++;
}
else
if(num[r]<num[l])
{
num[r-1] = num[r] + num[r-1];
r--;
ans++;
}
else
{
l++;
r--;
}
if(l>=r) break;
}
cout<<ans<<endl;
}
return 0;
}
相关文章
- c++ vector容器遍历方式
- C++类构造函数初始化列表
- 【转】c++数组初始化
- Win10系列:VC++ Direct3D模板介绍1
- C++学习之数组
- 转载 浅谈C/C++中的static和extern关键字
- C语言/C++常见习题问答集锦(四十七) 之字符串比较与分配宝藏
- 分糖果(C++)
- 读刘未鹏老大《你应当怎样学习C++(以及编程)》
- 【面试攻略】C++面试-IGG
- 【华为OD机试 2023最新 】计算数组中心位置(C++ 100%)
- 【华为OD机试 2023最新 】优雅子数组(C++ 100%)
- 【华为OD机试 2023】 计算数组中心位置(C++ Java JavaScript Python)
- c++将字符数组转成字符串
- char*动态数组用c++ifstream和ofstream进行文件读写并用memset初始化
- C++设计模式——状态模式(State)
- c++数组初始化‘0’
- c++子类重写父类方法
- C++格式化输出
- C++:读写二进制bin文件到double数组
- C/C++、Qt开发,跨平台CMake判断当前平台是Linux还是Windows,操作系统判断
- C++ stringstream学习
- C++逆向分析——对象拷贝
- C++ 数组
- 【c++复习笔记】——智能指针详细解析(智能指针的使用,原理分析)
- C++指向函数的指针数组
- C++使用技巧(二十四):回顾vector用法及多维数组使用