Codeforces 1036D 贪心

文章目录[x]
  1. 1:题目链接
  2. 2:题意
  3. 3:思路
  4. 4:参考代码

csdn博客链接:https://blog.csdn.net/nuoyanli/article/details/105107147

题目链接

https://codeforces.com/problemset/problem/1036/D

题意

给你两个数列,现在可以将数列中的连续的一些元素合并为一个元素。你现在的任务就是对这两个数列进行操作,使得这两个数列相等。求序列相等的最大长度,如果不能相等输出

思路

  • 如果两个数列和不一样,答案肯定是

  • 如果数列和一样,则一定有答案,至少也是,考虑贪心,直接从前到后枚举:

    如果直接后移

    如果使小的那个合并到他的下一个

    同理:如果

最后就是答案。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#define PB push_back
#define FI first
#define SE second
#define m_p(a, b) make_pair(a, b)
const double pi = acos(-1.0);
const double eps = 1e-9;
typedef long long LL;
const int N = 1e6 + 10;
const int M = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double f = 2.32349;
LL a[N], b[N];
void solve() {
  IOS;
  int n, m;
  cin >> n;
  LL suma = 0, sumb = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    suma += a[i];
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
    sumb += b[i];
  }
  if (suma != sumb) {
    cout << -1 << endl;
  } else {
    int ansn = n, ansm = m;
    int la = 1, lb = 1;
    while (la != n + 1 && lb != m + 1) {
      if (a[la] == b[lb]) {
        la++;
        lb++;
      } else if (a[la] < b[lb]) {
        a[la + 1] += a[la];
        la++;
        ansn--;
      } else {
        b[lb + 1] += b[lb];
        lb++;
        ansm--;
      }
    }
    cout << ansn << endl;
  }
}
signed main() {
  solve();
  return 0;
}
/*
49
18 1 7 2 1 1 50 22 8 2 2 1 30 2 46 10 1 4 5 18 25 21 38 11 2 15 29 8 7 2 45 12
14 16 16 23 11 1 1 4 48 18 3 1 1 23 4 10 7 50 5 25 34 22 19 4 4 2 40 52 1 4 1 3
47 9 4 1 8 47 4 5 1 1 9 22 9 2 2 1 1 48 7 2 8 16 4 2 41 12 3 30 21 10 2 2 5 1 31
13
*/

 

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像