L2-00 月饼

unsolved PTA C++ 贪心 所有文稿

关键词：贪心，比较函数的运用

一个非常重要的点：比较函数 (注意，必须用>或<，不可出现=，sort是不稳定排序)

/*22:45-23:00 部分错误*/
/*有一个测试用例段错误 没找出来bug*/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=1010;
struct Item{
    double kc,w;
    double d;
};//a[maxn];
bool cmpare(Item a,Item b){            //const必须加，不然会错，目前不懂为啥。当return的是ture时，a先输出，所以示例中是升序
        return a.d > b.d;
    }
int main(){
    int n,d;
    cin>>n>>d;
    Item* a=new Item[n];
    for(int i=0;i<n;i++) cin>>a[i].kc;
    for(int i=0;i<n;i++){
        cin>>a[i].w;
        a[i].d=a[i].w*1.0/a[i].kc;
    }
    sort(a, a+ n,cmpare);    
    //for(int i=0;i<n;i++) cout<<a[i].d<<endl;
    double tot=0.0;
    int now=0;
    while(1){
        if(a[now].kc<d){
            d-=a[now].kc;
            tot+=a[now].w;
            now++;
        }
        else{
            tot+=a[now].d*1.0*d;
            break;
        }
    }
    printf("%.2f",tot);
    system("pause");
    return 0;
}

以下是完全AC的程序，暂时没发现哪儿不同

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct Bean{
    double number; //销售量 
    double price; //售价 
    double unitPrice; //单价 
}; 
//排序比较函数 
int compare(Bean a,Bean b){
    return a.unitPrice > b.unitPrice;
} 
int main(){ 
    int n,i,j;
    double needs;
    cin>>n>>needs;
    Bean* beans=new Bean[n];
    for(i=0;i<n;i++){
        cin>>beans[i].number;
    }
    for(i=0;i<n;i++){
        cin>>beans[i].price;
        beans[i].unitPrice=beans[i].price/beans[i].number;
    }
    sort(beans,beans+n,compare); //按单价降序 
    double revenue=0;
    for(i=0;i<n;i++){
        if(needs<=beans[i].number){
            revenue+=beans[i].unitPrice*needs;
            break;
        }else{
            revenue+=beans[i].price;
            needs-=beans[i].number;
        }
    }
    printf("%.2lf\n",revenue);
} 

2019.3.16