头像

Hicode002

hicode




离线:22天前


最近来访(13)
用户头像
seoant
用户头像
TaoZex
用户头像
Henry_16
用户头像
Up_9
用户头像
这个网站哟西嘚斯
用户头像
暮冥
用户头像
Xkai
用户头像
芷澪酱
用户头像
1..
用户头像
zevzhang


Hicode002
1个月前
状态转移方程大家都知道
dp(i)=max(dp(j))+1
1<=j<i且a[j]<a[i]
当不存在合法j时就dp(i)=1
dp(1)=1

现在优化
看到a[j]<a[i] 下最大dp[j]
就发现可以用权值线段树维护
权值线段树维护的是每个a[i]下最大的dp[i]
然后要求的区间就是[负无穷,a[i]-1]的最大值
每算一个i就插入一个
要动态开点否则mle
注意的是dp(1)也要插入
就是a[1]插入1

C++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[100006],dp[100006],fa[100006];
inline void print(int lenfa){
    if(fa[lenfa]==lenfa){
        cout<<a[lenfa]<<" ";
        return;
    }
    print(fa[lenfa]);
    cout<<a[lenfa]<<" ";
}
struct node{
    int ls,rs;

    node(int l=0,int r=0){
        ls=l;
        rs=r;

    }
}tree[2000006];
int maxl[2000006];
int num=1;
inline void pushup(const int &o){
    maxl[o]=max(maxl[tree[o].ls ],maxl[tree[o].rs ]);
}

inline void inserts(const int&o,const int&l,const int&r,const int&x,const int&v){
    if(l==r){
        maxl[o]=max(maxl[o],v);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        if(!tree[o].ls ){
            tree[o].ls = ++num;

        }
        inserts(tree[o].ls ,l,mid,x,v);
    }else{
        if(!tree[o].rs ){
            tree[o].rs = ++num;
        }
        inserts(tree[o].rs ,mid+1,r,x,v);
    }
    pushup(o); 
}
inline int querymax(const int&o,const int&l,const int&r,const int&ql,const int&qr){
    if(o==0)return 0;
    if(ql<=l&&qr>=r){
        return maxl[o];
    }
    int mid=(l+r)>>1;
    int ans=0;
    if(ql<=mid){
        ans=max(ans,querymax(tree[o].ls ,l,mid,ql,qr));
    }
    if(qr>mid){
        ans=max(ans,querymax(tree[o].rs ,mid+1,r,ql,qr));
    }
    return ans;
}
int main(){
    for(int i=0;i<100006;++i)fa[i]=i;
    memset(dp,0,sizeof dp);
    int n;
    cin>>n;
    if(n==1){
        cout<<1<<endl;
        return 0;
    }
    for(int i=1;i<=n;++i)cin>>a[i];
    dp[1]=1;
    inserts(1,-1e9-1,1e9+1,a[1],1);
//  fa[1]=1;
    int len=0,lenfa=0;
    for(int i=2;i<=n;++i){

        dp[i]=querymax(1,-1e9-1,1e9+1,-1e9-1,a[i]-1) ;


        dp[i]+=1;
        inserts(1,-1e9-1,1e9+1,a[i],dp[i]);
        if(dp[i]>len){
            len=dp[i];
//          lenfa=i;
        }
    }
    cout<<len<<endl;

//  print(lenfa);
//  cout<<endl;
    return 0;
}


新鲜事 原文

Hicode002
1个月前
题解求和https://www.acwing.com/solution/content/63873/



Hicode002
1个月前

这是一道好题,之所以不在洛谷上写,是因为洛谷事太多了,逼着人用markdown

题意非常简单,就不介绍了

下面主要说一下思维过程和推导

【数据说明】 对于第 1 组至第 2 组数据,1 ≤ 𝑛 ≤ 100,1 ≤ 𝑚 ≤ 5;
对于第 3 组至第 4 组数据,1 ≤ 𝑛 ≤ 3000,1 ≤ 𝑚 ≤ 100

; 对于第 5 组至第 6 组数据,1 ≤ 𝑛 ≤ 100000,1 ≤ 𝑚 ≤ 100000,且不存在出现次数 超过 20 的颜色
; 对于全部 10 组 数 据 , 1 ≤ 𝑛 ≤ 100000,1 ≤ 𝑚 ≤ 100000,1 ≤ 𝑐𝑜𝑙𝑜𝑟𝑖 ≤ 𝑚,1 ≤ 𝑛𝑢𝑚𝑏𝑒𝑟𝑖 ≤ 100000

1.20pts

按照题意枚举x y z,然后判断是否符合3个条件,若满足,就统计分数,边做边取模

2.20pts的常数优化

对于x<y<z,我们可以不用判断是否满足,而是直接y从x+1枚举,z从y+1枚举,可以优化1/6 O(n^3)

3.40pts

y-x=z-y
2y=z+x
也就是说要满足这个式子,那么只需要x和z同奇偶
现在假设y>=z
2y>=2z
z+x>=2z
x>=z
不合题意
y<=x
2y<=2x
x+z<=2x
z<=x
x>=z
不合题意
所以只要x和z同奇偶且colorx=colorz且x<z
那么所有条件满足,直接统计分数

所以只要O(n^2)枚举x和z,判断条件并统计分数

40pts的常数优化

z从x+1枚举,优化1/2

进一步减少判断条件(60pts)

之前的枚举已经做到了极限,用枚举的原因是枚举能方便的判断
首先是colorx=colorz
那么我们就可以在读入时把每个颜色相同的编号放在一个数组里,不需要开二维数组(空间mle)
开一维数组加vector
然后发现枚举时要求编号同奇偶,所以同种颜色下再加一维存储奇数的编号和偶数的编号

这样由于是编号从小到大给出颜色,所以最终vector里的编号是严格递增的

这样就不需要任何判断了,也就是说只要枚举vector里的x,然后z=x+1开始枚举,
这样由于完全平方公式,复杂度又减小了,60pts


从枚举转向数学方法(100pts)

现在我们已经把枚举用到了极限,现在我们考虑分数,分数只与x z有关
score=(x+z)*(numx+numz)
我们考虑一个x对答案的贡献
(xi+x(i+1))*(numxi+numx(i+1))+(xi+x(i+2))*(numxi+numx(i+2))+...+(xi+x(end))*(numxi+numx(end))
拆开
第一项*第一项和
end-i-1+1=end-i
(end-i)*numxi*xi
第一项*第二项和
xi*(numxi+1  + ... +numxend)
第二项*第一项和:
numxi*(xi+1 +... + xend)
第二项*第二项和:
xi+1*numxi+1 + ... +xend*numxend
都可以用前缀和维护
分析复杂度:
输入O(n)
求前缀和O(n)
求答案O(n)
总O(n)
值得注意的是编号要从1开始
而vector从0开始,需要先push一个0

继续常数优化(时间+空间)

就是把vector的每个x贡献答案都加起来,推出公式
这样就不用前缀和数组了,空间减少了,且求前缀和和求答案一起求就可以了

求关注,求点赞谢谢!!!

C++ 代码(朴素100pts版本)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int p=10007;
int num[100006];
vector<int> coloryuan[100006][2];
vector<int>colornumsum[100006][2];
vector<int>colorxsum[100006][2];
vector<int>colorxnumsum[100006][2];
int ans=0;
int main(){
    int n,m;
    cin>>n>>m;
    if(n==1){
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i<=n;++i){
        cin>>num[i];
    }
    for( int i=1;i<=m;++i){

        coloryuan[i][0].push_back(0); 
        coloryuan[i][1].push_back(0); 
    }
    for( int i=1;i<=n;++i){
        int lin;
        cin>>lin;
        coloryuan[lin][i&1].push_back(i); 
    }
    for(int i=1;i<=m;++i){
        colorxnumsum[i][0].push_back(0) ;
        colorxnumsum[i][1].push_back(0) ;
        colorxsum[i][0].push_back(0) ;
        colorxsum[i][1].push_back(0) ;
        colornumsum[i][0].push_back(0) ;
        colornumsum[i][1].push_back(0) ;
        for(int j=1;j<coloryuan[i][0].size() ;++j){
//          cout<<1<<endl;
            colornumsum[i][0].push_back((colornumsum[i][0][j-1]%p+num[coloryuan[i][0][j]]%p)%p);
            colorxsum[i][0].push_back((colorxsum[i][0][j-1]%p+coloryuan[i][0][j]%p)%p);
            colorxnumsum[i][0].push_back((colorxnumsum[i][0][j-1]%p+(coloryuan[i][0][j]%p*(num[coloryuan[i][0][j]]))%p)%p);

        }
        for(int j=1;j<coloryuan[i][1].size() ;++j){
//          cout<<1<<endl;
            colornumsum[i][1].push_back((colornumsum[i][1][j-1]%p+num[coloryuan[i][1][j]]%p)%p);
            colorxsum[i][1].push_back((colorxsum[i][1][j-1]%p+coloryuan[i][1][j]%p)%p);
            colorxnumsum[i][1].push_back((colorxnumsum[i][1][j-1]%p+(coloryuan[i][1][j]%p*(num[coloryuan[i][1][j]]))%p)%p);

        }
    }

    for(int i=1;i<=m;++i){
        for(int j=1;j<coloryuan[i][0].size() ;++j){
//          cout<<1;
            ans+=((coloryuan[i][0].size()-1 -j)%p*(num[coloryuan[i][0][j]]%p))%p*(coloryuan[i][0][j]%p);
//          cout<<i<<" "<<coloryuan[i][0][j]<<" "<<colornumsum[i][0][j]
            ans%=p;
//          cout<<21;
            ans+=coloryuan[i][0][j]%p*((colornumsum[i][0][coloryuan[i][0].size() -1]-colornumsum[i][0][j]+p)%p);
//          cout<<1;
            ans%=p;
            ans+=num[coloryuan[i][0][j]]%p*((colorxsum[i][0][coloryuan[i][0].size() -1]-colorxsum[i][0][j]+p)%p);
            ans%=p;
            ans+=(colorxnumsum[i][0][coloryuan[i][0].size() -1]-colorxnumsum[i][0][j]+p)%p;
            ans%=p;
        }
        for(int j=1;j<coloryuan[i][1].size() ;++j){
//          cout<<1;
            ans+=((coloryuan[i][1].size()-1 -j)%p*(num[coloryuan[i][1][j]]%p))%p*(coloryuan[i][1][j]%p);
//          cout<<i<<" "<<coloryuan[i][0][j]<<" "<<colornumsum[i][0][j]
            ans%=p;

//          cout<<21;
            ans+=coloryuan[i][1][j]%p*((colornumsum[i][1][coloryuan[i][1].size() -1]-colornumsum[i][1][j]+p)%p);
//          cout<<1;
            ans%=p;
            ans+=num[coloryuan[i][1][j]]%p*((colorxsum[i][1][coloryuan[i][1].size() -1]-colorxsum[i][1][j]+p)%p);
            ans%=p;
            ans+=(colorxnumsum[i][1][coloryuan[i][1].size() -1]-colorxnumsum[i][1][j]+p)%p;
            ans%=p;
        }
    }
    cout<<ans<<endl;
    return 0;
}



Hicode002
3个月前

算法1

(数论数学) $O(1)$

那么实际上就是求a b均为正整数且互质时,ax+by 所不能表示的最大正整数(x,y>=0)
关键1
由无解想到有解
设ax+by 所不能表示的最大正整数(x,y>=0)为k
ax+by=k
定有整数解
证明:

k%gcd(a,b)=k%1=0

所以定有整数解
但是没有非负整数解
而x y都小于0时k也小于0,不行
x<0 y=0 || x=0 y<0也不行
只有(x<0 &&y>0)||(x>0&&y<0)

那么大于k的整数一定能被ax+by表示
设ax+by=k+a
此时x和y是这个不定方程的非负整数解

a(x-1)+by=k
y>=0
故x-1<0
x<1
0<=x<1
x=0
k=-a+by


关键2
把不定方程通解的性质运用到特解里
既然y无法确定取值
那么干脆设y=a+f
f为整数

 a+f>=0

 f>=-a

 k=-a+b(a+f)

  =-a+ab+bf

  =a(b-1)+bf

  b>=1

  所以b-1>=0

  所以f<0

  所以f<=-1

关键3
运用函数单调性

a(b-1)>=0
b>0
是单调递增
f=-1时k最大
k=ab-a-b

合法性:
-a<=f<=-1
a>=1
-a<=-1
合法
故答案为ab-a-b
注意longlong

时间复杂度

$O(1)$

C++ 代码

#include<iostream>
#include<cstdio>
using namespace std;

int main(){
    long long a ,b;
    cin>>a>>b;
    cout<<(a*b-a-b)<<endl;
    return 0;
}




Hicode002
11个月前

算法1

(dp) $O(tnm)$
Luogu5662纪念品
题面https://www.luogu.com.cn/problem/P5662
这道题没什么细节
是dp
考虑T=1时
显然一天无论怎么买怎么卖最后的值还是m,输出m
t=2很关键
两天时是完全背包
总体积是m,因为第一天买花费钱数必须不能超过m
单体积为第一天的价格
单价值为第二天-第一天价格,显然当有物品的单价值<0时意味着买卖这个物品会赔钱,所以跳过这个物品,不参与dp
而每个物品可以买无限个
所以是完全背包而非01背包
进行完全背包
最后dp[m]为最大利润
输出m+dp【m】

推广到一般情况
当第i天买第k天卖
由于每天可以无限次买卖
所以相当于第i天买第i+1天卖第i+1天再买,第i+2天再卖
所以2天2天的完全背包
把每次完全背包后的利润加在一起
m也要随之更新
每一次完全背包m都要加上这次的利润
最后输出和

注意:!!dp数组的大小不是纪念品的个数而是总体积大小,所以开到10^4而非100,在这里wa了一次

时间复杂度

完全背包优化后为$O(nm)$
n是物品个数,m是体积(这里m为金币数)
执行t-1次
所以为$O(tnm)$

C++ 代码


#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[10009],a[103][103];
using namespace std;
int main(){
    int t,n,m;
    cin>>t>>n>>m;
    for(int i=1;i<=t;++i){
        for(int j=1;j<=n;++j){
            cin>>a[i][j];
        }
    }
    //int tot=0;
    for(int i=1;i<=t-1;++i){
        memset(dp,0,sizeof dp);
        int v=m;
        for(int j=1;j<=n;++j){
            int vi=a[i][j];
            int wi=a[i+1][j]-a[i][j];
            if(wi<=0)continue;
            for(int z=vi;z<=v;++z){
                dp[z]=max(dp[z],dp[z-vi]+wi);
            }
        }
        m=m+dp[v];

    }
    cout<<m<<endl;
    return 0;
}



Hicode002
11个月前

算法1

(暴力枚举) $O(玄学)$
Luogu5661公交换乘
题面https://www.luogu.com.cn/problem/P5661
模拟题
注意几点
只有乘地铁才会获得优惠券,优惠券只能用来乘公交车
优惠卷有效期45分钟
使用优惠券除了时间限制还有价格限制,只有当前公交车票价<=优惠券价格才能用
优惠券可以累积---------队列
如果可以使用优惠券则一定使用优惠券,并且优先用最早的合法优惠券,这意味着在优惠券合法的情况下,先用最早获得的
在最早的优惠券不合法的情况下,一定向后找合法的优惠券,如果找不到就代表这次公交车不使用优惠券(去年就栽在这)


所以一个双端deque结构体队列,存时间与价格,坐地铁时入队,统计地铁价格,坐公交时检查队列并出队
不能用普通队列因为queue不能用迭代器
规则:
当公交车时间-队头时间>45时不断出队直到公交车时间-队头时间<=45或队空(如果这次公交车-队头时间都大于45那么后面的公交车-队头时间也大于45,所以这样的优惠券作废)
若队空直接加上此次公交车价格
若队不空,开始检查价格
如果队头价格>=公交车价格就出队并跳过本次循环(使用了优惠券)
否则就用stl的iterator迭代器从队头开始向后遍历整个队列直到找到一个优惠券价格大于等于公交车价格
那么就用stl的erase删除掉这个优惠券(注意erase左闭右开erase(i,i+1)代表删除i)
然后跳过本次循环
如果遍历完队列找不到合法优惠券就直接加上此次公交车价格


最后输出价格和。

时间复杂度

O(n)~O(玄学)

C++ 代码

#include<iostream>
#include<cstdio>
#include<iterator>
#include<deque>
#include<queue>
using namespace std;
struct p{
    int t;//time
    int w;//price

};
deque<p>pro;
int main(){
    int n,tot=0;
    cin>>n;
    for(int i=0;i<n;++i){
        int tran;
        cin>>tran;
        p po;
        cin>>po.w>>po.t ;
        if(tran==0){//sub
            pro.push_back(po);
            tot+=po.w;
        }else{//bus
            while(1){
                if(!pro.empty() ){
                    if(po.t-pro.front().t>45){
                        pro.pop_front() ;
                    }else{
                        break;
                    }
                }else{
                    break;
                }
            }
            if(pro.empty() ){
                tot+=po.w;
                continue;
            }
            if(po.w<=pro.front().w){
                pro.pop_front() ;
                continue;
            }else{
                deque<p> ::iterator to;
                int fl=1;
                for(to=pro.begin() ;to!=pro.end() ;++to){
                    if(po.w >(*to).w){
                        continue;
                    }else{
                        fl=0;
                        pro.erase(to,to+1); 
                        break;
                    }
                }
                if(fl){
                    tot+=po.w;
                }else{
                    continue;
                }
            }


        }
    }
    cout<<tot<<endl;
    return 0;
}


新鲜事 原文

Hicode002
2020-08-28 02:40
有人吗? n/ln n=k 已知k怎么求n 近似值即可



Hicode002
2019-12-14 06:30

算法1

(暴力枚举) $O(nk)$

这道题很坑,40分很好做,只要桶排一遍即可,70分只要桶排前挑出符合时间的即可,100分用到stl了,用queue存每个人的时间与国籍,每次找不符合时间的,把它出队,桶内–;
注意:
1.struct存时间和国籍
2.统计的是不符合时间的而不是符合时间的
3.每次以前一次的统计为基础,减去不符合时间的不同国籍数就是这次的不同总人数
4.queue要记得判断是否empty(),不直接调用front(),这样会re,当queue 空时,只需统计这次国籍不同数量即可,不用找之前的。

参考文献

C++ 代码

#include<iostream>//can`t
#include<cstdio>//can`t
#include<cstring>//can`t
#include<string>//can`t
#include<cmath>
#include<fstream>
#include<sstream>
#include<ctime>//can`t
#include<cstdlib>//can`t
#include<cfloat>//can`t
#include<climits>//can`t
#include<iomanip>
#include<stack>//can`t
#include<queue>//can`t
#include<deque>//can`t
#include<map>//can`t
#include<set>//can`t
#include<bitset>//can`t
#include<vector>//can`t
#include<algorithm>//can`t
#define ll long long
#define ui unsigned
#define re register
#define fop(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define fc() fclose(stdin),fclose(stdout)

using namespace std;//can`t

inline void myread(int&x){
    char a,f=1;
    x=0;
    a=getchar();
    if(a>='0'&&a<='9')x=a-48;
    else if(a=='-')f=-1;
    while(1){
        a=getchar();
        if(a>='0'&&a<='9')x=x*10+a-48;
        else {x=x*f;return;
        }
    }
}
inline void mywrite(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)mywrite(x/10);
    putchar(x%10+48);
}
struct people{
    int time,ji;
};
queue<people>port;
int gjs[100007];
void tests(const int& totp){
    cout<<'\n';
    for(re int i=0;i<100007;++i){

        if(gjs[i]!=0)cout<<"test:"<<i<<" geshu:"<<gjs[i]<<' ';
    }
    cout<<endl<<"totp:"<<totp<<"\n";
}
int main(){
    memset(gjs,0,sizeof(gjs));
    int n,totp=0;
    myread(n);
    for(re int i=0;i<n;++i){
        int t,k;
        myread(t),myread(k);
        if(!port.empty() ){

            while(1){
                if(port.empty() ||port.front() .time>t-86400)break;

                else{

                    --gjs[port.front() .ji];
                    if(gjs[port.front() .ji]==0)--totp;
                    port.pop() ;

                }
            }
        }
        for(re int j=0;j<k;++j){
            int x;
            myread(x);
            people lin;
            lin.ji =x;
            lin.time =t;
            port.push(lin);
            if(gjs[x]==0)++totp;
            ++gjs[x];
        //  tests(totp);
        }
        mywrite(totp),putchar('\n');
    }
    return 0;
}





Hicode002
2019-12-07 05:33

样例

in:
5 1 1

out:
1


算法1

(暴力枚举、模拟) $O((n+1)/2)$

这道题很简单,不用找很多规律,太难了,更不要开二维数组(mle),其实只要模拟一下,并且找一个简单规律即可
首先我们发现一个矩阵有固定圈数,偶数时为n/2,奇数时(n+1)/2,整合得(n+1)/2
然后找到发现每一圈的格数为4(t-1)(t为一行的格数)
再发现从最外一圈每向内缩一圈,t就-=2
每一圈只有4个情况:
1.第i行第e列(i为每圈首行)
2.第e行第i列(i为每圈首列)
3.第e行第in列(in为每圈末列)
4.第in行第e列(in为每圈末行)
所以枚举即可

时间复杂度

总共进行2次循环,第一次为圈数$(n+1)/2$,第二次为i,j所在圈数次,所以总时间复杂度约等于2*n,舍掉2得$O(n)$

C++ 代码

#include<iostream>//can`t
#include<cstdio>//can`t
#include<cstring>//can`t
#include<string>//can`t
#include<cmath>
#include<fstream>
#include<sstream>
#include<ctime>//can`t
#include<cstdlib>//can`t
#include<cfloat>//can`t
#include<climits>//can`t
#include<iomanip>
#include<stack>//can`t
#include<queue>//can`t
#include<deque>//can`t
#include<map>//can`t
#include<set>//can`t
#include<bitset>//can`t
#include<vector>//can`t
#include<algorithm>//can`t
#define ll long long
#define ui unsigned
#define re register
#define fop(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define fc() fclose(stdin),fclose(stdout)

using namespace std;//can`t

inline void myread(int&x){
    char a,f=1;
    x=0;
    a=getchar();
    if(a>='0'&&a<='9')x=a-48;
    else if(a=='-')f=-1;
    while(1){
        a=getchar();
        if(a>='0'&&a<='9')x=x*10+a-48;
        else {x=x*f;return;
        }
    }
}
inline void mywrite(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)mywrite(x/10);
    putchar(x%10+48);
}
int main(){
    #ifdef DEBUG
    fop(matrix);
    #endif
    int n,x,y,fl=-1,fl1=-1,fl2=-1;
    cin>>n>>x>>y;
    int q=(n+1)/2;
    for(re int i=1,j=n;i<=q;++i,--j){
        if(x==i&&y>=i&&y<=j){
            fl=i;
            fl1=j;
            fl2=1;
            break;
        }else if(y==j&&x>=i&&x<=j){
            fl=i;
            fl1=j;
            fl2=3;
            break;
        }else if(x==j&&y>=i&&y<=j){
            fl=i;
            fl1=j;
            fl2=4;
            break;
        }else if(y==i&&x>=i&&x<=j){
            fl=i;
            fl1=j;
            fl2=2;
            break;
        }
    }
    int ans=0;
    for(re int i=1,j=n;i<fl;++i,j-=2){
        ans+=4*j-4;

    }

    if(fl2==1){
        cout<<ans+1+(y-fl);
    }else if(fl2==3){
        int r=ans+1+(fl1-fl);
        cout<<x-fl+r;
    }else if(fl2==4){
        int rs=ans+1+(fl1-fl);
        int rss=rs+fl1-fl;
        cout<<rss+(fl1-y);
    }else if(fl2==2){
        int ra=ans+1+(fl1-fl);
        int raa=ra+fl1-fl;
        int raaa=raa+fl1-fl;
        cout<<fl1-x+raaa;
    }

    fc();
    return 0;
}//hicode002所有,禁止抄袭





Hicode002
2019-11-10 08:47

题目描述

样例



算法1

(暴力枚举) $O(n)$

水题不水啊

坑点:
1.爆$int$,开$long long$
2.注意暴力时不要枚举一次就重新计算气势值,这样会超时

时间复杂度

$O(N)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define ll long long
#define re register
ll a[N];//num of bing
int main(){
    ll n,m,p1,s1,s2,ls=0,hs=0;
    scanf("%lld",&n);
    for(re ll i=1;i<=n;++i){
        scanf("%lld",&a[i]);
    }
    scanf("%lld%lld%lld%lld",&m,&p1,&s1,&s2);
    a[p1]+=s1;
    for(re ll i=1;i<m;++i){
        ls+=a[i]*(m-i);
    }
    for(re ll i=m+1;i<=n;++i){
        hs+=a[i]*(i-m);
    }
    long long mini=0,minn=LLONG_MAX;

    for(re ll i=1;i<=n;++i){
          if(i<m){
            if(abs(ls+s2*(m-i)-hs)<minn){
                minn=abs(ls+s2*(m-i)-hs);
                mini=i;
            }
          }
          if(i==m){
            if(abs(ls-hs)<minn){//不要写成加号
                minn=abs(ls-hs);//不要写成加号
                mini=i;
              }
          }
          if(i>m){
            if(abs(hs+s2*(i-m)-ls)<minn){
                minn=abs(hs+s2*(i-m)-ls);
                mini=i;
              }
          }
    }
    cout<<mini<<endl;
    return 0;
}