NOIP2018普及T2暨洛谷P5016 ***
题目链接:https://www.luogu.org/problemnew/show/P5016
分析:
这是一道模拟题。看到题目,我们首先要把它细致的读明白,模拟题特别考察细节,往往会有想不到的坑点(好吧,这题貌似没有)。
然后我们还要看一看数据范围,可以注意到会出现10^9级别的数字。稍有信息学常识的人都知道,int型存储的最大数字是2147483647(再加就爆富负了),实在背不过这个数字也没关系,只要记住大概 109级别即可,所以这题就可以long long了。
考虑到只需要开一个 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;
}