B3999[洛谷 202406GESP模拟四级]锣鼓工厂
首先，理解题目，我们可以很容易得知，本题 似乎 要使用贪心算法
一定要注意：
今天的锣鼓如果有剩余就可以挪到明天用
真的被骗惨了，反复提交数次
我们可以定义几个结构体，因为题目要求输出编号，我们可以使用结构体进行存储编号，方便输出
具体思路：
1.根据输入排序（升序）
bool cmp1(chevie a,chevie b){
return a.val<b.val;
}bool cmp2(buy a,buy b){
return a.val<b.val;
}
for(int i=1;i<=n;i++){
cin>>a[i].val;
a[i].x=i;
}for(int i=1;i<=n;i++){
cin>>b[i].val;
b[i].x=i;
}
sort(a+1,a+n+1,cmp1);
sort(b+1,b+n+1,cmp2);
2.遍历每一笔订单，如果无法交付，则直接输出“No”
同时定义一个tmp来存储上一次剩余的锣鼓数
bool flag;
int tmp=0;
for(int i=1;i<=n;i++){
flag=true;
for(int j=1;j<=n;j++){
if(a[j].val+tmp>=b[i].val&&a[j].used==false){
a[j].used=true;
c[i].ch=a[j].x;
c[i].d=b[i].x;
tmp=a[j].val+tmp-b[i].val;
flag=false;
break;
}
}if(flag==true){
break;
}
}
3.如果可以，输出方案
if(flag==true){
cout<<"No"<<endl;
}else{
cout<<"Yes"<<endl;
for(int i=1;i<=n;i++){
cout<<c[i].ch<<' ';
}cout<<endl;
for(int i=1;i<=n;i++){
cout<<c[i].d<<' ';
}cout<<endl;
}
啊！多么精简的思路！写起来一定很简单吧
（本人代码习惯的确是丛林土鳖，莫要嫌弃）
完整 AC Code:
/**********亿点点************/
#include<bits/stdc++.h>
using namespace std;
struct chevie{ //机器信息
int val; //日产量
int x; //编号
int used; //是否使用过
}a[1010];
struct buy{ //订单
int val; //订单量
int x; //编号
}b[1010];
struct ways{ //交付方式
int ch; //机器编号
int d; //订单编号
}c[1010];
bool cmp1(chevie a,chevie b){//排序方式（无需多言）
return a.val<b.val;
}bool cmp2(buy a,buy b){
return a.val<b.val;
}int main(){
int T;
cin>>T;
for(int l=1;l<=T;l++){
for(int i=1;i<=1000;i++) a[i].used=false;//不要忘初始化
int n;
cin>>n;
for(int i=1;i<=n;i++){ //输入（无需多言）
cin>>a[i].val;
a[i].x=i;
}for(int i=1;i<=n;i++){
cin>>b[i].val;
b[i].x=i;
}sort(a+1,a+n+1,cmp1); //排序（无需多言）
sort(b+1,b+n+1,cmp2);
bool flag;
int tmp=0; //昨天剩的锣鼓数
for(int i=1;i<=n;i++){ //直接遍历！！！
flag=true;
for(int j=1;j<=n;j++){
if(a[j].val+tmp>=b[i].val&&a[j].used==false){
a[j].used=true;
c[i].ch=a[j].x;
c[i].d=b[i].x;
tmp=a[j].val+tmp-b[i].val;
flag=false;
break;//找到了就走
}
}if(flag==true){ //什么！你找不到！走吧
break;
}
}if(flag==true){ //什么！你找不到！
cout<<"No"<<endl;
}else{ //找到了！！！
cout<<"Yes"<<endl;
for(int i=1;i<=n;i++){ //控制一下格式
cout<<c[i].ch<<' ';
}cout<<endl;
for(int i=1;i<=n;i++){
cout<<c[i].d<<' ';
}cout<<endl;
}
}
return 0;
}
无注释纯享版：
#include<bits/stdc++.h>
using namespace std;
struct chevie{
int val;
int x;
int used;
}a[1010];
struct buy{
int val;
int x;
}b[1010];
struct ways{
int ch;
int d;
}c[1010];
bool cmp1(chevie a,chevie b){
return a.val<b.val;
}bool cmp2(buy a,buy b){
return a.val<b.val;
}int main(){
int T;
cin>>T;
for(int l=1;l<=T;l++){
for(int i=1;i<=1000;i++){
a[i].used=false;
}
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].val;
a[i].x=i;
}for(int i=1;i<=n;i++){
cin>>b[i].val;
b[i].x=i;
}sort(a+1,a+n+1,cmp1);
sort(b+1,b+n+1,cmp2);
bool flag;
int tmp=0;
for(int i=1;i<=n;i++){
flag=true;
for(int j=1;j<=n;j++){
if(a[j].val+tmp>=b[i].val&&a[j].used==false){
a[j].used=true;
c[i].ch=a[j].x;
c[i].d=b[i].x;
tmp=a[j].val+tmp-b[i].val;
flag=false;
break;
}
}if(flag==true){
break;
}
}if(flag==true){
cout<<"No"<<endl;
}else{
cout<<"Yes"<<endl;
for(int i=1;i<=n;i++){
cout<<c[i].ch<<' ';
}cout<<endl;
for(int i=1;i<=n;i++){
cout<<c[i].d<<' ';
}cout<<endl;
}
}
return 0;
}