博客
关于我
Codeforces B. Nastya and Door (前缀和优化) (Round #637 Div.2)
阅读量:170 次
发布时间:2019-02-28

本文共 1788 字,大约阅读时间需要 5 分钟。

要解决这个问题,我们需要找到一个长度为k的山脉子段,其中包含最多的峰。峰被定义为数组中一个元素大于其前后两个元素的值。我们需要在所有这样的子段中,找到起始位置最小的那个。

方法思路

  • 前缀和数组预处理:创建一个前缀和数组pos,其中pos[i]表示从数组开始到索引i的位置有多少个峰。
  • 计算峰数:遍历数组,计算每个位置是否是峰,并更新前缀和数组。
  • 遍历子段:对于每个可能的子段起始位置l,计算该子段包含的峰数。记录最大峰数和对应的起始位置l。
  • 优化计算:使用前缀和数组,使得每个子段的峰数计算为O(1)时间复杂度。
  • 解决代码

    #include 
    #define endl '\n'#define null NULL#define ll long long#define pii pair
    #define lowbit(x) (x & (-x))#define ls(x) << 1#define rs(x) (x << 1 | 1)#define me(ar) memset(ar, 0, sizeof(ar))#define mem(ar, num) memset(ar, num, sizeof(ar))#define rp(i, n) for(int i = 0, i < n; i++)#define rep(i, a, n) for(int i = a; i <= n; i++)#define pre(i, n, a) for(int i = n; i >= a; i--)#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int inf = 0x7fffffff;const double PI = acos(-1.0);const double eps = 1e-6;const ll mod = 1e9 + 7;const int N = 2e5 + 5;int t, n, k, a[N], pos[N];signed main() { IOS; cin >> t; while (t--) { cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; } pos[0] = 0; for (int i = 2; i <= n; i++) { if (a[i] > a[i-1] && a[i] > a[i+1]) { pos[i] = pos[i-1] + 1; } else { pos[i] = pos[i-1]; } } int ans = 0, l = -1; for (int i = 1; i + k - 1 <= n; i++) { int cnt = pos[i + k - 1] - pos[i - 1]; if (cnt > ans) { ans = cnt; l = i; } else if (cnt == ans && i < l) { l = i; } } cout << ans << " " << l << endl; } return 0;}

    代码解释

  • 初始化和输入处理:读取输入数据,初始化数组pos和其他变量。
  • 前缀和数组计算:遍历数组,计算每个位置是否是峰,并更新前缀和数组pos。
  • 遍历子段:检查每个可能的子段起始位置l,计算该子段的峰数,并记录最大值和对应的起始位置。
  • 输出结果:根据计算结果,输出最大峰数和最小的起始位置l。
  • 这种方法的时间复杂度为O(n),能够高效处理较大的输入规模。

    转载地址:http://osdj.baihongyu.com/

    你可能感兴趣的文章
    Python_生产者消费者模型、管道、数据共享、进程池
    查看>>
    python_程序格式_缩进_行注释_段注释---python工作笔记012
    查看>>
    python_程序的构成---python工作笔记015
    查看>>
    python_超文本传输协议
    查看>>
    Python_集合
    查看>>
    Python|AsyncIO|TypeError:应为协程
    查看>>
    python——random模块的应用
    查看>>
    Python——基础知识细节
    查看>>
    Python——正则表达式
    查看>>
    Python—面向对象2
    查看>>
    Python“和“带整数的运算符
    查看>>
    Python“文件存在“制作目录时出错
    查看>>
    Python“文件存在“制作目录时出错
    查看>>
    Python、IMAP 和 GMail.将消息标记为已查看
    查看>>
    python一个一个获取迭代器的元素
    查看>>
    python一维数组 提取_python – 如何从numpy中的1维数组中提取零维切片
    查看>>
    python三大库之--numpy(一)
    查看>>
    python三大库之--numpy(二)
    查看>>
    python上的字无效字符_标识中的无效字符
    查看>>
    python下用decode和encode 中文转码
    查看>>