• Codeforces Round #802 (Div. 2)


    C题-Helping the Nature

    在这里插入图片描述
    在这里插入图片描述

    思路

    • 直接的思路:使得每棵相邻树的高度相同。做法只能是对每棵相邻的树,根据大小处理前缀或后缀之一,相同高度为两者的较小值,且这些处理序列一个也不能少。
    • 差分的思路(转):
      在这里插入图片描述其中 d 1 = a [ 1 ] − a [ 0 ] d_1 = a[1] - a[0] d1=a[1]a[0],其中 a [ 0 ] = 0 a[0]=0 a[0]=0

    看到区间操作就想到前缀和和差分。属于常用套路

    #include <bits/stdc++.h>
    using namespace std;
    #include<stack>
    #define int long long
    signed main()
    {
        int t;
        cin >> t;
        for(int i = 0;i<t;i++)
        {
            int n;
            cin >> n;
            int a[n];
            for(int k = 0;k<n;k++) cin>>a[k];
            int ans = 0;
            int temp = a[n - 1];
            for(int k = n - 1;k>=1;k--)
            {
                if(a[k] - a[k - 1] >= 0)  //后缀相减使其等于前缀
                {
                    ans += (a[k] - a[k - 1]);
                    temp -= (a[k] - a[k - 1]);
                }
                else
                {
                    ans += (a[k - 1] - a[k]);
                }
            }
            cout << ans + abs(temp) << endl;
        }
        system("pause");
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    D题-Helping The Nature

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    思路

    • 必要条件减小搜索空间
    • 找是否能满足DP

    D P [ i ] DP[i] DP[i],处理到第i个lock,前i个lock全部开启,并装满前i个lock所需要的最短时间。guess:

    • 若第i个lock能在前面i-1个lock装满的时间之前或刚好装满,则 D P [ i ] = D P [ i − 1 ] DP[i] = DP[i-1] DP[i]=DP[i1]
    • 否则,前i-1个lock溢出的水与第i个lock管道的水会相互混合。可看作是前i个管道向前i个lock注水。所需时间 ⌈ s u m ( v [ 1 : i ] ) i ⌉ \lceil \frac{sum(v[1:i])}{i}\rceil isum(v[1:i])

    所以 D P [ i ] = m a x ( D P [ i − 1 ] , ⌈ s u m ( v [ 1 : i ] ) i ⌉ ) DP[i] = max(DP[i-1],\lceil \frac{sum(v[1:i])}{i}\rceil) DP[i]=max(DP[i1],isum(v[1:i]))
    对每个query,必要条件是 t q u e r y > = d p [ n ] t_{query} >= dp[n] tquery>=dp[n].在这样的时间段内,若取q个管道,可保证有充足的时间将这前q个装满。

    • 若开启前q个管道而在 d p [ n ] dp[n] dp[n]的时间内所有水库已经装满,则q一定满足条件。且一定有 t q u e r y ⋅ q ≥ d p [ n ] ⋅ q ≥ s u m ( v [ 1 : n ] ) t_{query} \cdot q \geq dp[n] \cdot q\geq sum(v[1:n]) tqueryqdp[n]qsum(v[1:n])
    • 否则可看作前q的管道同时注水,速率混合。因此需要保证在 t q u e r y t_{query} tquery的时间内,以q速率,能将水库注满,也有: t q u e r y ⋅ q ≥ s u m ( v [ 1 : n ] ) t_{query} \cdot q \geq sum(v[1:n]) tqueryqsum(v[1:n])

    因此给定q,只需检查
    t q u e r y ⋅ q ≥ s u m ( v [ 1 : n ] ) t_{query} \cdot q \geq sum(v[1:n]) tqueryqsum(v[1:n])是否满足即可。找到最小这样的q即可。

    #include <bits/stdc++.h>
    using namespace std;
    #include<stack>
    #define int long long
    signed main()
    {
        int n;
        cin >> n;
        int v[n];
        int prev[n + 1];
        prev[0] = 0;
        for(int i = 0;i<n;i++) 
        {
            scanf("%ld",&v[i]);
            prev[i + 1]  = prev[i] + v[i];
        }
        int dp[n + 1];
        dp[1] = v[0];
        for(int i = 2;i<=n;i++) dp[i] = max(dp[i - 1],(long long)ceil((double)prev[i] / i));
        int q;
        cin >> q;
        for(int i = 0;i<q;i++)
        {
            int t;
            scanf("%ld",&t);
            if(t < dp[n]) printf("-1\n");
            else   //找到第一个大于等于ceil(prev[n]/t)的prefixsum之和
            {
                t = (int)ceil((double)prev[n]/t);
                printf("%ld\n",t);
            }
        }
        system("pause");
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
  • 相关阅读:
    大型电厂IP互联无线对讲通信解决方案
    遗传算法解决TSP问题(附matlab源程序)
    kingbase之ksql命令工具
    jinja2.exceptions.UndefinedError: ‘None‘ has no attribute ‘id‘
    【无标题】LeetCode题解:19. 删除链表的倒数第 N 个结点,JavaScript,详细注释
    linux系统学习笔记9——CANOpen状态转换
    数学才是顶级码农的核心修养,码农怎样搞好数学?来看看这些网友强推的数学神作!文末评论区进行评论参与送书哟
    【UCB操作系统CS162项目】Pintos Lab2:用户程序 User Programs(上)
    vite基础概述+搭建vue项目基础框架+Vant组件库
    MySQL项目实战——用户行为分析
  • 原文地址:https://blog.csdn.net/nth2000/article/details/125443130