2019 校内赛 RPG的天赋分支(贪心)

Problem Description

很多游戏都有天赋树的概念，天赋树的不同分支具有不同的属性加成，那么合理选择分支就非常重要了。
Luke最近沉迷一款RPG游戏，它的天赋树机制如下：

角色具有n个可选天赋，天赋之间不存在任何依赖，每个可选天赋有左右两条分支，对于任意天赋，只能选择某一条分支，左右分支所提升的属性值分别是a和b。现在角色需要决定每个天赋的选择，游戏要求选择A个左分支和 B个右分支（n=A+B），每个天赋只可以点一次。问如何分配天赋点数使得提升属性最大化。

Input

第一行为正整数t表示测试组数。
随后为t组输入，每组测试中，第一行为整数n A B分别表示总天赋数，左右分支的数目要求，随后n行每行两个正整数a b分别表示左、右分支的属性加成。
t<=300    
n<=10^6  
A+B=n    
0<=a,b<=10^9

Output

对于每组测试数据，输出一行整数表示最大的属性加成。

Sample Input

1

3 1 2

6 1

3 1

7 4

Sample Output

11

思路:根据内部的差值从小到大排序 小的就选另一边(r个) 和自己这边l个 的和

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<string>

#include<vector>

#include<stack>

#include<bitset>

#include<cstdlib>

#include<cmath>

#include<set>

#include<list>

#include<deque>

#include<map>

#include<queue>

#define ll long long int

using namespace std;

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int moth[]={,,,,,,,,,,,,};

int dir[][]={, ,, ,-, ,,-};

int dirs[][]={, ,, ,-, ,,-, -,- ,-, ,,- ,,};

const int inf=0x3f3f3f3f;

const ll mod=1e9+;

int n,l,r;

struct node{

    int a,b;

};

node p[];

bool cmp(node a,node b){

    return a.a-a.b<b.a-b.b;

}

int main(){

    ios::sync_with_stdio(false);

    int t;

    cin>>t;

    while(t--){

        cin>>n>>l>>r;

        for(int i=;i<=n;i++)

            cin>>p[i].a>>p[i].b;

        sort(p+,p+n+,cmp);

        ll ans=;

        for(int i=;i<=r;i++)

            ans+=p[i].b;

        for(int i=n;i>=n-l+;i--)

            ans+=p[i].a;

        cout<<ans<<endl;

    }

    return ;

}