题目描述
blablabla
样例
blablabla
算法1
(直接模拟) $O(n)$
直接计算左右两边的总和,判断s2放哪个位置,当左右相同时,放m位置就可以,当左边大于右边考虑放右边的位置使差值最小,如果达不到差值最小,还是放m位置,右边大于左边相同,还有这个可能爆了int,得开long long
时间复杂度分析:直接一轮,O(n)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, ll> PII;
const int N = 1e5 + 10;
PII a[N];
ll m, n, p1, s1, s2;
ll sum1, sum2;
ll ans;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i].first);
}
scanf("%d%d%d%d", &m, &p1, &s1, &s2);
a[p1].first+=s1;
for(int i = 1; i < m; i++)
{
a[i].second = (m-i)*a[i].first;
sum1+=a[i].second;
}
for(int i = m+1; i <= n; i++)
{
a[i].second = (i-m)*a[i].first;
sum2+=a[i].second;
}
if(sum1 == sum2)
{
cout << m << endl;
return 0;
//cout << 1 << endl;
}
else if(sum1 < sum2)
{
ll Min = abs(sum2-sum1);
for(int i = 1; i < m; i++)
{
ll k = sum1;
k-=a[i].second;
ll num = a[i].first;
num+=s2;
ll v = num*(m-i);
if(abs(k+v-sum2) <= Min)
{
ans = i;
Min = abs(k+v-sum2);
}
}
//cout << 2 << endl;
}
else
{
ll Min = abs(sum2-sum1);
for(int i = m + 1; i <= n; i++)
{
ll k = sum2;
k-=a[i].second;
ll num = a[i].first;
num+=s2;
ll v = num*(i-m);
if(abs(k+v-sum1) <= Min)
{
ans = i;
Min = abs(k+v-sum1);
}
}
}
if(ans == 0)
{
cout << m << endl;
}
else
cout << ans << endl;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度分析:blablabla
C++ 代码
blablabla