题目链接

题意理解

显然，第$i+1$ 位大臣拿的钱比第$i$ 位大臣多

记$i-1$位大臣拿的钱为$c_{i-1}$ ，第$i$ 位大臣和第$i+1$位大臣拿的钱可以分别表示出来。此时顺序是，$i-1, i, i+1$ ①

然后交换第$i$ 位大臣和第$i+1$位大臣。此时顺序是$i-1, i+1, i$②

此时我们希望第$i+1$位大臣排在后面拿的钱要少与第$i$ 位大臣排在后面的前，此时就有不等式了

代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class People implements Comparable{int l;int r;public People(int l, int r) {this.l = l;this.r = r;}@Overridepublic int compareTo(Object o) {People people = (People)o;return Math.min(this.l, people.r) - Math.min(this.r, people.l);}}
public class Main {static int T;static int n;static People[] peoples;public static void main(String[] args) {FastScanner fs = new FastScanner();T = fs.nextInt();while(T-->0) {long sum = 0;long[] dp = new long[50050];dp[0] = 0;n = fs.nextInt();peoples = new People[n];for(int i = 0; i < n; i++) {int x = fs.nextInt();int y = fs.nextInt();peoples[i] = new People(x, y);}Arrays.sort(peoples);for(int i = 0; i < n; i++) {sum += peoples[i].l;dp[i] = Math.max(dp[Math.max(0, i - 1)], sum) + peoples[i].r;}System.out.println(dp[n-1]);}}public static class FastScanner {private BufferedReader br;private StringTokenizer st;public FastScanner() {br = new BufferedReader(new InputStreamReader(System.in));}public String nextToken() {while(st == null || !st.hasMoreElements()) {try {st = new StringTokenizer(br.readLine());} catch (Exception e) {// TODO: handle exception}}return st.nextToken();}public int nextInt() {return Integer.valueOf(nextToken());}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！