USACO23OPEN-Silver A

题目来源

洛谷：USACO23OPEN-Silver Milk Sum(A)

SPOJ：USACO23OPEN-Silver Milk Sum(A)

题解： USACO23OPEN-Silver Milk Sum(A)

题面简述

$\qquad$给定数组 $a_1,…,a_N$ ，在数组中依次选出一个元素构成排列 $b_1,…,b_N$ 。

$\qquad$定义 $T = \sum _{i=1} ^N i \times b_i$ 。

$\qquad$现在给出 $Q$ 个操作，每个操作有两个数 $s$ 和 $k$ 表示将 $a_s$ 替换成 $k$ ，对于每一个操作求出操作后的 $T$ 的最大值，每次操作后数组还原成原样。

题目描述

$\qquad$农民约翰的 $N$ 头奶牛的产奶量为整数 $a_1,……,a_N$。也就是说，第 $i$ 头奶牛每分钟产奶 $a_i$ 单位。

$\qquad$每天早上，农场主约翰开始把牲口棚里的 $N$ 头牛都拴在挤奶机上。他被要求一个接一个地解开它们，把它们送出去进行日常锻炼。他送出去的第一头奶牛在挤奶一分钟后就会解开钩，送出去的第二头奶牛在挤奶一分钟后就会解开钩，以此类推。因为第一头奶牛（例如奶牛$x$）在挤奶机上只花了 $1$ 分钟，所以她只贡献了 $a_x$ 单位的总牛奶。第二头奶牛（比如奶牛$y$）在挤奶机上总共花了 $2$ 分钟，因此贡献了 $2∗ay$ 单位的总牛奶。第三头奶牛（比如奶牛$z$）贡献了 $3a_z$ 个单位，以此类推。假设 $T$ 代表农场主约翰按最优顺序解开奶牛，他总共能收集到的最大牛奶量。

$\qquad$农场主约翰很好奇，如果他的奶牛群的牛奶产量有所不同，会受到什么影响。对于每个 $Q$ 查询，每个查询由两个整数 $i$ 和 $j$ 指定，请计算如果 $a_i$ 设置为 $j$，$T$ 的新值将是什么。注意，每个查询都考虑一个临时的潜在变化，独立于所有其他查询；也就是说，$a_i$ 在考虑下一个查询之前恢复到其原始值。

输入格式

第一行输入一个整数 $N$ 。

第二行输入 $N$ 个整数 $a_1\dots a_N$ 。

第三行输入一个整数 $Q$ 。

接下来有 $Q$ 行，每行两个整数 $i$ 和 $j$ 。

输出格式

输出共有 $Q$ 行，每行一个整数，依次表示第 $Q$ 次查询的所对应的 $T$ 值。

题解

言简意赅，该题有几个性质：

将 $a$ 数组按从小到大顺序排列， ;
对于每次操作，可以用 $lower_bound$ 求得修改值在数组 $b$ 中的位置；
考虑每次修改对 $ans$ 的影响 ，分 $3$ 种情况讨论，设 $x$ 表示修改的位置对应的 $a[s]$ 在 $b$ 数组的位置，设 $y$ 表示修改的值 $k$ 在 $b$ 数组中的位置，分 $x<y$ , $x=y$ , $x>y$ 三种情况枚举即可。

代码

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 151234;
int sum[N],ans;
int n,q,a[N],b[N];
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    cin>>n;For(i,1,n) a[i]=b[i]=input();
    sort(b+1,b+n+1);
    For(i,1,n) sum[i]=sum[i-1]+b[i],ans+=i*b[i];
    cin>>q;
    while(q--){
        int k=input(),w=input(),res=0;
        int x=lower_bound(b+1,b+n+1,a[k])-b;
        int y=lower_bound(b+1,b+n+1,w)-b;
        if(x==y) res=ans-b[x]*x+w*y;else
        if(x>y) res=ans+sum[x-1]-sum[y-1]-b[x]*x+w*y;
        else res=ans-(sum[y-1]-sum[x])-b[x]*x+w*(y-1);
        cout<<res<<'\n';
    }
    return 0;
}