15. 北理工的恶龙

北理工的恶龙"/>

15. 北理工的恶龙

 思路：

我们可以将恶龙分为两类，一类是经验值为正数的，一类是负数的，根据贪心原则，收获的经验越多越好，故我们将正负分开存储，将正数部分的武力值从小到大排序，之后我们从小到大打败，如果经验值不够就氪金，之后加上恶龙给的经验值。

对于负数部分来说，我们打完这条龙剩下的经验值必然大于等于这条龙的经验值（负数）加上难度值因此根据贪心原则，剩下的经验值越大就可以氪金越少，故我们按照难度值和经验之和从大到小排序，之后我们从大到小打败，如果经验值不够就氪金，之后加上恶龙给的经验值。

代码：

#include <iostream>  
#include <algorithm>  
using namespace std;  
pair<int,int>p[300010];  
pair<long long,int> st[300010];  
int idx;  
#define x first  
#define y second  
int main()  
{  int n;  cin>>n;  for(int i=1;i<=n;i++){  cin>>p[i].x;  cin>>p[i].y;  }  sort(p+1,p+n+1);  long long k=0;  long long exp=0;  for(int i=1;i<=n;i++){  if(p[i].y>=0){  if(p[i].x>exp)k+=p[i].x-exp,exp=p[i].x;  exp+=p[i].y;  }  if(p[i].y<0){  st[++idx]={p[i].x+p[i].y,i};  }  }   sort(st+1,st+idx+1);  for(int i=idx;i>=1;i--){  int  t=st[i].y;  if(p[t].x>exp)k+=p[t].x-exp,exp=p[t].x;  exp+=p[t].y;  }  cout<<k<<endl;  return 0;  
}