【AcWing】100. IncDec序列

2021-06-06 20:04

阅读：758

标签：for math return www. names pos 题解相对 round

题目链接：

给定一个长度为 $n$

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

tips：

　　1.进行问题求解的等价转换---对a数组区间的操作等价转换为对b数组其中两个元素（端点）的操作

　　2.数据范围求和后可能爆，用 long long

　　3.变成一样的，只考虑2...n---由b数组的定义可知，b[1]=a[1]；其他b[i]=a[i]-a[i-1];

　　代码中直接用a的空间来存b了，b[i]存储记录的是a[i]比a[i-1]大的相关信息，对a[i]和a[i-1]的相对大小关系进行了建模。

　　4.差分+贪心；差分：前缀和的逆运算

　　5.对每次操作的区间进行了范围讨论[i,j]是否在[2,n];

　　6.求最小次数下的方案数最后成为一个排列组合问题

　　7.疑问：为什么不考虑最后m对应的b数组的几个位置？？

其他好的题解：

　　ref1

　　ref2

#include 
#include 

using namespace std;

typedef long long LL;

const int N = 100010;

int a[N];

int main(){
    
    int n;
    cin >> n;
    for (int i = 1; i > a[i];
    for(int i = n; i > 1; i --) a[i] = a[i] - a[i-1];//倒着处理--mark
    
    LL pos = 0, neg = 0;
    for (int i = 2; i  )
        if (a[i] > 0 ) pos += a[i];
        else neg-=a[i]; //求负数的绝对值之和
    cout  endl;
    cout 1  endl;
    
    return 0;
    
}

View Code

专注于过程，沉浸其中。对于终究要做的事，要选择性的忽略这件事消耗的时间，赶紧去做，告别拖延。

【AcWing】100. IncDec序列

标签：for math return www. names pos 题解相对 round

原文地址：https://www.cnblogs.com/SUMaywlx/p/10765795.html

上一篇：这可能是史上最全的windows10装ubuntu双系统教程

下一篇：C#事件订阅及触发例子

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【AcWing】100. IncDec序列
文章链接：http://soscw.com/index.php/essay/91425.html

亲，登录后才可以留言！

【AcWing】100. IncDec序列

评论

热门文章

推荐文章

最新文章

置顶文章