上海计算机学会10月月赛丙组T3对称合并题解
对称合并
内存限制: 256 Mb时间限制: 1000 ms
题目描述
数列 α1,α2,…,αnα1,α2,…,αn 的逆转定义为 αn,αn−1,…,α1αn,αn−1,…,α1。
如果一个数列与它的逆转完全一样，则称该数列对称。
例如 1,2,2,11,2,2,1 以及 123,456,123123,456,123 都是对称的，但 121,212121,212 不是。
给定一个数列 A1,A2,…,ANA1,A2,…,AN，请问至少需要进行几次合并操作，才能将这个数列变成对称？
所谓合并操作就是在数列中选择两个相邻的数字，删除它们，然后将它们的和插入到删除的位置。
输入格式
- 第一行：单个整数表示 NN
- 第二行：NN 个整数表示 A1,A2,…,ANA1,A2,…,AN
输出格式
- 单个整数表示答案。
数据范围
- 对于 30%30% 的数据，N≤10N≤10。
- 对于 60%60% 的数据，N≤103N≤103。
- 对于 100%100% 的数据，1≤N≤1061≤N≤106
- 1≤Ai≤1091≤Ai≤109。
题解：
用两个指针
i=1, j=N，分别从两端开始比较
A[i]和A[j]：如果相等：
i++, j--，继续比较下一对如果不相等：我们需要合并使得它们相等
如果
A[i] < A[j]：合并左边的A[i]和A[i+1]，使左边和增大如果
A[i] > A[j]：合并右边的A[j-1]和A[j]，使右边和增大
每次合并操作计数加1
直到
i >= j#include <iostream> #include <vector> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; vector<long long> A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } int i = 0, j = N - 1; long long left_sum = 0, right_sum = 0; int operations = 0; while (i < j) { if (left_sum == 0) left_sum = A[i]; if (right_sum == 0) right_sum = A[j]; if (left_sum == right_sum) { left_sum = 0; right_sum = 0; i++; j--; } else if (left_sum < right_sum) { operations++; left_sum += A[i + 1]; i++; } else { // left_sum > right_sum operations++; right_sum += A[j - 1]; j--; } } cout << operations << endl; return 0; }