K签个到(贪心)第十五届中北大学算法与程序设计竞赛

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了K签个到(贪心)第十五届中北大学算法与程序设计竞赛，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1075字，纯文字阅读大概需要2分钟。

内容图文

题目链接：https://ac.nowcoder.com/acm/contest/5188/K

题目大意：

给定 n个正整数：a1,a2...an?1,an。每次操作可以选择数组中任意一个数加上或减去其下标。
求 m次操作后，数组中最大值与最小值的差最大可能是多少。
(1<=n<=100000,0<=m<=100000)
(?100000<=ai<=100000)

题解：贪心

直觉就是 m次操作在同一个数上是最优的

答案就是a[i]+m*i-a(min)和a(max)-(a[i]-i*m)中更大的那一个

代码：

#include<iostream>
#include<cstdio> 
#include<cstring>
#include<algorithm>
#define N 100009
#define LL long long
using namespace std;
 
LL n,m;

struct P
{
    LL x,id; 
}a[N]; 

bool cmp(P c,P d)
{
    return c.x<d.x;
}

int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
    //    scanf("%d",&a[i].x);
        cin>>a[i].x;
        a[i].id=i;
    }
    if(n==1)
    {
        cout<<'0';
        return 0;
    }
    sort(a+1,a+n+1,cmp);
//    LL mx=-10000000000,mx_;
//    LL mn=10000000000,mn_;
    LL mx=a[1].x+m*a[1].id;
    LL mn=a[1].x-m*a[1].id; 
    for(LL i=1;i<=n;i++)
    {
        if(a[i].x+m*a[i].id>mx) mx=a[i].x+m*a[i].id;
        if(a[i].x-m*a[i].id<mn) mn=a[i].x-m*a[i].id;
    }
  //  cout<<mx<<"---"<<mn<<endl;
    LL ans1=mx-a[1].x;
    LL ans2=a[n].x-mn;
    if(ans1-ans2>0) cout<<ans1;
    else cout<<ans2;
    return 0;
}
 /*我傻了*/

View Code

 

内容总结

以上是互联网集市为您收集整理的K签个到(贪心)第十五届中北大学算法与程序设计竞赛全部内容，希望文章能够帮你解决K签个到(贪心)第十五届中北大学算法与程序设计竞赛所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---