PAT 1070

阳光穿透心脏的1/2处 2022-03-07 12:52 244阅读 0赞

clipboard.png
简单的贪心问题，和背包问题类似，这里不再赘述

  1. #include<iostream>
  2. #include<stdlib.h>
  3. #include<stdio.h>
  4. #include<vector>
  5. #include<cmath>
  6. #include<algorithm>
  7. using namespace std;
  8. using std::vector;
  9. const int maxn=1010;
  10. struct node{
  11.     double num;
  12.     double price;
  13. };
  15. bool cmp(node a,node b){
  16.     return a.price>b.price;
  17. }
  19. node moc[maxn];
  20. int n;
  21. double m;
  22. int main(){
  23.     double p;
  24.     scanf("%d%lf",&n,&m);
  25.     for(int i=0;i<n;i++){
  26.         scanf("%lf",&moc[i].num);
  27.     }
  28.     for(int i=0;i<n;i++){
  29.         scanf("%lf",&p);
  30.         moc[i].price=p/moc[i].num;
  31.     }
  32.     sort(moc,moc+n,cmp);
  33.     double money=0;
  34.     for(int i=0;i<n;i++){
  35.         if(m==0)
  36.             break;
  37.         if(moc[i].num<=m){
  38.             money+=moc[i].price*moc[i].num;
  39.             m-=moc[i].num;
  40.         }else{
  41.             money+=m*moc[i].price;
  42.             m=0;
  43.         }
  44.     }
  45.     printf("%.2f\n",money);
  46.     system("pause");
  47.     return 0;
  48. }

发表评论

表情：
评论列表 （有 0 条评论，244人围观）

还没有评论，来说两句吧...

相关阅读

    相关 PAT~乙级~1070 结绳 ~Python

    目描述： 给定一段一段的绳子，你需要把它们串成一条绳。每次串连的时候，是把两段绳子对折，再如下图所示套接在一起。这样得到的绳子又被当成是另一段绳子，可以再次对折去跟另一...

    妖狐艹你老母妖狐艹你老母/ 0 赞/ 136 阅读

    相关 【杭电1070】Milk

    ![这里写图片描述][20160721084340435] ![这里写图片描述][20160721084352546] 最重要的思想是在输入的时候去掉多余的输入数据。

    冷不防冷不防/ 0 赞/ 258 阅读

    相关 1070. 结绳(25)

    给定一段一段的绳子，你需要把它们串成一条绳。每次串连的时候，是把两段绳子对折，再如下图所示套接在一起。这样得到的绳子又被当成是另一段绳子，可以再次对折去跟另一段绳子串连。每次串

    本是古典 何须时尚本是古典 何须时尚/ 0 赞/ 233 阅读