贪心

首先我们可以把所有的东西分成两类

一个是加血的，一个是扣血的

那显然是先搞加血的

然后再将每个加血的以需要的血量从小到大排序

然后再把每个扣血的按照回血的从小到大排序

#include<algorithm>
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int N=1e5+20;
int n,s,cnt1=0,cnt2=0,now=0,anscnt=0;
int ans[N];
struct node{
	int x,y,id;
}a[N],b[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
bool cmp1(node a,node b){
	if(a.x==b.x) return a.y>b.y;
	return a.x<b.x;
}
bool cmp2(node a,node b){return a.y>b.y;}
signed main(){
	n=reads(),s=reads();
	for(int i=1;i<=n;i++){
		int p,q;
		p=reads(),q=reads();
		if(q>=p) a[++cnt1].x=p,a[cnt1].y=q,a[cnt1].id=i;
		else b[++cnt2].x=p,b[cnt2].y=q,b[cnt2].id=i;
	}
	sort(a+1,a+cnt1+1,cmp1);
	sort(b+1,b+cnt2+1,cmp2);
	now=s;
	for(int i=1;i<=cnt1;i++){
		if(now-a[i].x<=0){
			puts("-1");
			exit(0);
		}
		else{
			now=now-a[i].x+a[i].y;
			ans[++anscnt]=a[i].id;
		}
	}
	for(int i=1;i<=cnt2;i++){
		if(now-b[i].x<=0){
			puts("-1");
			exit(0);
		}
		else{
			now=now-b[i].x+b[i].y;
			ans[++anscnt]=b[i].id;
		}
	}
	for(int i=1;i<=anscnt;i++) printf("%lld ",ans[i]);
	return 0;
}

贪心好题

坑点

• 在任意时刻，你的血量不能为零或为负。 是的，为0也不可以，所以判断的时候用"<="

 if (s<=x[i].a) {
   	cout<<-1<<'\n';
   	return;
   }

思路

考虑让s先尽可能增加，达到最大值时再减。

增加：先把a<=b的敌人打败，这样每次都可以增加血量。但打敌人的时候，要保证s>a，考虑以a从小到大排序，如果出现s<=a，就输出“-1”

减小：剩下a>b的敌人，无论我们怎么打，都会减少固定的血量和增加固定的回血量，考虑让回血量尽可能大，最后一个敌人浪费的回血量尽可能小，即以b从大到小排序

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long

namespace syr
{
	const ll N = 1e5+10;
	struct node {
		ll id;
		ll a;
		ll b;
	}x[N];
	ll n, s, tot;
	ll v[N], ans[N];
	bool cmp (node a, node b) {
		if (a.a==b.a) return a.b>b.b;
		return a.a<b.a;
	}
	bool cmp2 (node a, node b) {
		return a.b>b.b;
	}
	void work()
	{
		cin>>n>>s;
		for (ll i=1; i<=n; i++) {
			cin>>x[i].a>>x[i].b;
			x[i].id = i;
		}
		sort(x+1, x+1+n, cmp);
		for (ll i=1; i<=n; i++) {
			if (x[i].a>x[i].b) continue;
			v[x[i].id] = 1;
			if (s<=x[i].a) {
				cout<<-1<<'\n';
				return;
			}
			s = s-x[i].a+x[i].b;
			ans[++tot] = x[i].id;
		}
		sort(x+1, x+1+n, cmp2);
		for (ll i=1; i<=n; i++) {
			if (v[x[i].id]) continue;
			if (s<=x[i].a) {
				cout<<-1<<'\n';
				return;
			}
			s = s-x[i].a+x[i].b;
			ans[++tot] = x[i].id;
		}
		for (ll i=1; i<=n; i++)
			cout<<ans[i]<<" ";
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	syr::work();
	return 0;
}

打游戏 题解

题意简述

消灭 n 个敌人，消耗ai点，得到bi点。初始时，有s点血量。在任意时刻，血量不能为零或为负。问：如何安排消灭敌人的顺序，可以使得游戏顺利通关？不能，-1。

分析

本题一眼贪心，BUT考场上是可怜的68pts。。。发现是一部分排序的贪心思想错了。。(悲

1. 将敌人分成回血（ai<bi）和扣血（ai>bi）两类。
2. 先打回血的部分敌人。
3. 打扣血的部分时无需考虑差值！！！不能只考虑扣血！！必须先打回血多的，这样才有可能继续打下面的！！！
4. 随时判断是否血量>0，注意必须在扣血后马上判断！！！不能等到回血以后！！！

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int n,s,ss,sum,cnt1,cnt2,ans[N],cnt;
struct node{
	int id,a,b;
}t[N],aa[N],bb[N];
bool cmp1(node x,node y){
	if(x.a==y.a)return x.b>y.b;
	return x.a<y.a;
}
bool cmp2(node x,node y){
	if(x.b==y.b)return x.a<y.a;
	return x.b>y.b;//先打回血多的！ 
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>s;
	for(int i = 1;i<=n;i++){
		cin>>t[i].a>>t[i].b;
		t[i].id=i;
		if(t[i].a<=t[i].b)aa[++cnt1]=t[i];//增生命值
		else bb[++cnt2]=t[i];//减生命值
	}
	ss=s;
	sort(aa+1,aa+1+cnt1,cmp1);
	sort(bb+1,bb+1+cnt2,cmp2);
	for(int i = 1;i<=cnt1;i++){
		ans[++cnt]=aa[i].id;
		ss=ss-aa[i].a;
		if(ss<=0){
			cout<<-1<<'\n';
			return 0;
		}
		ss+=aa[i].b;
	}
	for(int i = 1;i<=cnt2;i++){
		ans[++cnt]=bb[i].id;
		ss=ss-bb[i].a;
		if(ss<=0){
			cout<<-1<<'\n';
			return 0;
		}
		ss+=bb[i].b;
	}
	for(int i = 1;i<=n;i++)cout<<ans[i]<<' ';
	return 0;
}

贪心

每次都选能打的中最大回升的敌人

其中能打的是h中的元素

因为要减少的值是一定的，所以我们要每一次选择增长最多的

code:

#include <bits/stdc++.h>
using namespace std;

const long long N = 1e5 + 10;

struct A {
	long long a, b, id;
	friend bool operator < (A x,A y) {
		return x.a > y.a;
	}
} arr[N];

struct B {
	long long a, b, id;
	friend bool operator < (B x,B y) {
		return x.b < y.b;
	}
};

long long n, s;

void read() {
	cin >> n >> s;
	for(long long i = 1; i <= n; i++) {
		cin >> arr[i].a >> arr[i].b;
		arr[i].id = i;
	}
	return ;
}

priority_queue<A> q;

priority_queue<B> h;

vector<long long> ans;

void compute() {
	for(long long i = 1; i <= n; i++) {
		q.push(arr[i]);
	}
	for(long long i = 1; i <= n; i++) {
		while(q.size() && q.top().a < s) {
			A tmp = q.top();
			q.pop();
			B qq;
			qq.a = tmp.a;
			qq.b = tmp.b;
			qq.id = tmp.id;
			h.push(qq);
		}
		if(h.size() == 0){
			cout << -1;
			return ;
		}
		B tmp = h.top();
		h.pop();
		s -= tmp.a;
		if(s <= 0){
			cout << -1;
			return ;
		}
		s += tmp.b;
		ans.push_back(tmp.id);
	}
	for(long long i = 1;i <= n; i++){
		cout << ans[i-1] << ' ';
	}
	return ;
}

int main() {
//	freopen("aaa.in","r",stdin); 
//	freopen("aaa.out","w",stdout); 
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	read();
	compute();
	return 0;
}

家人们，我是 xixisuper。

贪心。我们把怪物分为两种：净扣咱血的和净回咱血的（包括不扣的）。

我们容易发现净回血的怪我们最开始全把它们打了是不劣的，我们将这部分怪按照 $a_i$ 为关键字从小到大打掉，如果打不掉就无解。以上是显然的，我们考虑如何弄那些净扣血的，显而易见，我们应该以 $b_i$ 为关键字从大到小排序怪物即可，因为扣血和回血的总量是固定的，为了尽量不浪费回血我们应该保证最后一个怪的回血最少减少浪费，以此类推往上从大到小即可了。

题解简陋请见谅毕竟：

讲的越模糊，讲得越好。——w*****g

代码：

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
const ll N=1e5+5;
ll n,s;
struct node{
	ll a,b,id;
	friend bool operator < (const node a,const node b){
		if(a.b==b.b) return a.a<b.a;
		return a.b>b.b;
	}
}a[N];
ll ans[N],idx;
vector<node> q1,q2;
inline bool cmp(node a,node b){return a.a<b.a;}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>s;
	for(ll i=1;i<=n;i++){
		cin>>a[i].a>>a[i].b;
		a[i].id=i;
		if(a[i].a<=a[i].b) q1.push_back(a[i]);
		else q2.push_back(a[i]);
	}
	sort(q1.begin(),q1.end(),cmp);
	sort(q2.begin(),q2.end());
	for(auto x:q1){
		if(x.a>=s){cout<<-1;return 0;}
		s-=x.a;s+=x.b;
		ans[++idx]=x.id;
	}
	for(auto x:q2){
		if(x.a>=s){cout<<-1;return 0;}
		s-=x.a;s+=x.b;
		ans[++idx]=x.id;
	}
	for(ll i=1;i<=idx;i++) cout<<ans[i]<<' ';
	return 0;
}