企业官网建设流程全解析

对称合并

内存限制: 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; }