Codeforces-1462D Add to Neighbour and Remove


Problem

Portal


Thoughts

由于数据范围不大,我们可以枚举最终数的大小,预处理出前缀和。
同时我们可以发现操作次数=序列数的个数-段数。
设序列个数为n,有k组,每组有x1,x2,…,xk个数,每组需要xi-1次操作,操作总数为x1-1+x2-1+x3-1+…+xk-1=n-k。
那么当我们答案数越大且存在,那么段数一定会变小。
所以我们只要找到第一个合理的答案,就break即可,当前解就是最优解。


Accepted Code

#include <bits/stdc++.h>

using namespace std;

const int N = 3010;

int a[N], s[N];

int main()
{
    int T; cin >> T;
    while(T -- )
    {
        int n; cin >> n;
        for(int i = 1 ; i <= n ; i ++ ) 
        {
            cin >> a[i];
            s[i] = s[i - 1] + a[i];
        }

        int ans = 0, flag = 0;
        for(int i = 1 ; i <= n ; i ++ )
        {       
            int t = 0;
            ans = 0;
            for(int j = 1 ; j <= n ; j ++ )
            {
                t += a[j];
                if(t > s[i]) break;

                if(t == s[i])
                {
                    t = 0, ans ++ ;
                    if(j == n) 
                    {
                        flag = 1;
                        break;
                    }
                }
            }

            if(flag) break;
        }

        cout << n - ans << endl;
    }

    return 0;
}

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
Codeforces-1462E1 Close Tuples (easy version) Codeforces-1462E1 Close Tuples (easy version)
ProblemPortal Accepted Code#include <bits/stdc++.h> #define int long long using namespace std; const int N = 20001
Next 
Codeforces-1461C Random Events Codeforces-1461C Random Events
ProblemPortal Thoughts直接算能排序的概率很困难,那我们就算操作之后不能排序的概率p,再用1-p。那怎么让其无法排序呢?我们先将序列排序,找到排序序列和原序列最后一个不相同的位置pos,在小于pos的r都是没用的,所以
  TOC