嗯...
题目链接:https://www.luogu.org/problem/P5016
这道题是一道模拟,不要考虑复杂,直接暴力枚举每一个点,看看加上s2之后两个势力的差值,找最小,记录下标。
注意数据很大,用long long, 最小值的初始值要足够大。
AC代码:
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 5 using namespace std; 6 7 long long n, p1, s1, s2, sum1, sum2, ans = 1e19, m, now, t1, t2, tmp; 8 long long c[10000005]; 9 10 int main(){ 11 scanf("%lld", &n); 12 for(int i = 1; i <= n; i++) scanf("%lld", &c[i]); 13 scanf("%lld%lld%lld%lld", &m, &p1, &s1, &s2); 14 c[p1] += s1; 15 for(int i = 1; i <= m - 1; i++) sum1 += c[i] * (m - i); 16 for(int i = m + 1; i <= n; i++) sum2 += c[i] * (i - m); 17 if(sum1 == sum2) {printf("%lld", m); return 0;} 18 for(int i = 1; i <= n; i++){ 19 t1 = sum1, t2 = sum2; 20 if(i < m) t1 += (m - i) * s2; 21 else t2 += (i - m) * s2; 22 tmp = abs(t1 - t2); 23 if(tmp < ans) {ans = tmp; now = i;} 24 } 25 printf("%lld", now); 26 return 0; 27 }