思想
基于贪心的思想,对于每一个操作将0~x个数变成y,优先选择y值较大的操作,所以将操作op根据y值从大到小排序。为了总和最大,需要尽可能小的数变成y,所以还需要将数从小到大排序。
代码
import java.io.*;
import java.util.Arrays;
public class Main{
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N = (int)1e5+10;
static Integer[] a = new Integer[N];
static PII[] op = new PII[N];
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
public static void main(String[] args)throws IOException{
int n = nextInt(), m = nextInt();
for(int i=0; i<n; i++) a[i] = nextInt();
for(int i=0; i<m; i++) op[i] = new PII(nextInt(), nextInt());
Arrays.sort(a, 0, n);
Arrays.sort(op, 0, m, (o1, o2)->(o2.y - o1.y)); //先处理y较小的操作
int pos = 0; //操作的起始位置
for(int i=0; i<m; i++){
int cnt = op[i].x; //选择处理的最大数量
while(pos<n && cnt>0 && a[pos]<op[i].y){
a[pos++] = op[i].y;
cnt--;
}
}
long ans = 0;
for(int i=0; i<n; i++) ans = ans+a[i];
out.println(ans);
out.flush();
out.close();
}
}
class PII{
int x, y;
public PII(int x, int y){
this.x = x;
this.y = y;
}
}