NOIP2018普及T2暨洛谷P5016 ***

题目链接:https://www.luogu.org/problemnew/show/P5016

分析:

这是一道模拟题。看到题目,我们首先要把它细致的读明白,模拟题特别考察细节,往往会有想不到的坑点(好吧,这题貌似没有)。

然后我们还要看一看数据范围,可以注意到会出现10^9级别的数字。稍有信息学常识的人都知道,int型存储的最大数字是2147483647(再加就了),实在背不过这个数字也没关系,只要记住大概 1 0 9 10^9 109级别即可,所以这题就可以long long了。

考虑到只需要开一个 1 0 5 10^5 105级别的数组,所以全部long long就好(方便)。

我们顺着题目的思路,先求出每一方的气势,并不用记录每一个点的气势(别忘了p1点要先加上s1),然后我们可以先计算出两者之差(取个绝对值就不用考虑那么多了),由于要计算最小值,所以记录那个值的QAQ要赋一个最大值。然而我们并不需要多么大,考虑到最后两方之差总要减去一个加上的气势,所以最大值只需要赋成s。。。

然后后面就是简单的分情况讨论,别忘了从小到大,这样能满足最小的序号

代码:

#include<cstdio>
#include<cmath>
using namespace std;
#define maxn 100005
long long n,m,c[maxn],p1,ans,s1,s2,l,r,QAQ;
int main()
{
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++)scanf("%lld",&c[i]);
    scanf("%lld%lld%lld%lld",&m,&p1,&s1,&s2);
    c[p1]+=s1;
    for(long long i=1;i<m;i++) l+=c[i]*(m-i);
    for(long long i=m+1;i<=n;i++) r+=c[i]*(i-m);
    long long s=abs(l-r);
    QAQ=s;
    ans=m;
    if(l>r)
    {
        for(long long i=m+1;i<=n;i++)
        {
            if(abs(s-s2*(i-m))<QAQ)
            {
                QAQ=abs(s-s2*(i-m));
                ans=i;
            }
        }
    }
    else
    {
        for(long long i=1;i<m;i++)
        {
            if(abs(s-s2*(m-i))<=QAQ)
            {
                QAQ=abs(s-s2*(m-i));
                ans=i;
            }
        }
    }
   	printf("%lld",ans);
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
11-27 10:46
点赞 评论 收藏
分享
11-15 18:39
已编辑
西安交通大学 Java
全村最靓的仔仔:卧槽,佬啥bg呢,本也是西交么
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务