结构体+sort+贪心算法正解

作为2025年的最后一次GESP考级，25年的考级也圆满画上了句号，我也想给大家讲解一下哈！

首先来分析一下题目：
【题干】
商店有小A有$M$元的预算，让你帮他买东西，要求如下：

1.V越小代表商品的优先级越高。
2.总是优先买优先级最高的东西；
3.如果有多个最高优先级商品，购买价格最低的；
4.如果有多个优先级最高且价格最低的商品，购买商品名字典序最小的。(注意是字典序！！！）

【输入/输出】
第一行两个正整数$M,N$，代表预算和商品数。
之后 N 行，每行一个商品，依次为$S_i,P_i,V_i$，代表第 i 个商品的商品名、价格、优先级。
数据保证不存在两个名字相同的商品。

按照字典序从小到大的顺序，输出所有购买商品的商品名。

【数据】
良心数据，良心到不必多说。（1~4级GESP的数据不会为难人）

如下是主函数上的代码

struct pai{//定义结构体
	string name;
	int p,v;
}a[1005];
bool cmp(pai x,pai y){
	if(x.v!=y.v){
		return x.v<y.v;
	}
	if(x.p!=y.p){
		return x.p<y.p;
	}
	return x.name<y.name;
}//如何排序
string s[1005];

如下是主函数下的代码

int m,n;
cin>>m>>n;
for(int i=1;i<=n;i++){
	cin>>a[i].name>>a[i].p>>a[i].v;//输入
】
}
sort(a+1,a+1+n,cmp);
int cnt=0;
for(int i=1;i<=n;i++){
     if(m>=a[i].p){
	     m-=a[i].p;
	     cnt++;
	     s[cnt]=a[i].name;
	 }
	 else if(m>0){
		   continue;
	 }
		else{
			break;
	    }//判断shi作为2025年的最后一次GESP考级，25年的考级也圆满画上了句号，我也想给大家讲解一下哈！

首先来分析一下题目：
【题干】
商店有小A有$M$元的预算，让你帮他买东西，要求如下：
```cpp
1.V越小代表商品的优先级越高。
2.总是优先买优先级最高的东西；
3.如果有多个最高优先级商品，购买价格最低的；
4.如果有多个优先级最高且价格最低的商品，购买商品名字典序最小的。(注意是字典序！！！）

【输入/输出】
第一行两个正整数$M,N$，代表预算和商品数。
之后 N 行，每行一个商品，依次为$S_i,P_i,V_i$，代表第 i 个商品的商品名、价格、优先级。
数据保证不存在两个名字相同的商品。

按照字典序从小到大的顺序，输出所有购买商品的商品名。

【数据】
良心数据，良心到不必多说。（1~4级GESP的数据不会为难人）

如下是主函数上的代码

struct pai{//定义结构体
	string name;
	int p,v;
}a[1005];
bool cmp(pai x,pai y){
	if(x.v!=y.v){
		return x.v<y.v;
	}
	if(x.p!=y.p){
		return x.p<y.p;
	}
	return x.name<y.name;
}//如何排序
string s[1005];

如下是主函数下的代码

int m,n;
cin>>m>>n;
for(int i=1;i<=n;i++){
	cin>>a[i].name>>a[i].p>>a[i].v;//输入
】
}
sort(a+1,a+1+n,cmp);
int cnt=0;
for(int i=1;i<=n;i++){
     if(m>=a[i].p){
	     m-=a[i].p;
	     cnt++;
	     s[cnt]=a[i].name;
	 }
	 else if(m>0){
		   continue;
	 }
		else{
			break;
	    }//判断式
	}
    sort(s+1,s+cnt+1);
	for(int i=1;i<=cnt;i++){
	    cout<<s[i]<<endl;
	}

下面是全代码：

#include<bits/stdc++.h>
using namespace std;
struct pai{
	string name;
	int p,v;
}a[1005];
bool cmp(pai x,pai y){
	if(x.v!=y.v){
		return x.v<y.v;
	}
	if(x.p!=y.p){
		return x.p<y.p;
	}
	return x.name<y.name;
}
string s[1005];
int main(){
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].name>>a[i].p>>a[i].v;
	}
	sort(a+1,a+1+n,cmp);
	int cnt=0;
	for(int i=1;i<=n;i++){
        if(m>=a[i].p){
	        m-=a[i].p;
	        cnt++;
	        s[cnt]=a[i].name;
	    }
		else if(m>0){
		    continue;
	    }
		else{
			break;
	    }	
	}
    sort(s+1,s+cnt+1);
	for(int i=1;i<=cnt;i++){
	    cout<<s[i]<<endl;
	}
	return 0;
}

点个赞吧