13 条题解

  • 9
    @ 2023-8-12 12:33:44

    P1029

    -题目回顾-

    阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 NN 堆金币，第 ii 堆金币的总重量和总价值分别是mi mi 。阿里巴巴有一个承重量为 TT 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

    -分析-

    如果黄金总重量小于背包承重量，则直接输出黄金总价值。所以我们可以定义两个变量储存黄金总重量和总价值

    -代码-

    #include <bits/stdc++.h>//by AGOMG(hetao1193656)
using namespace std;
struct Jin{
    double V, M;
    double tot;
}a[1000];
bool cmp(Jin a, Jin b){
    return a.tot > b.tot;
}int main(){
    int n, s = 0;
    float ss = 0;
    double t;
    cin >> n >> t;
    for (int i = 0; i < n; i++){
        cin >> a[i].M >> a[i].V;
        s += a[i].M;
        ss += a[i].V;
        a[i].tot = a[i].V / a[i].M;
    }sort(a, a + n, cmp);
    int pos = 0;
    float sum = 0;
    if(s <= t){cout << fixed << setprecision(2) << ss;return 0;}
    while (t > 0){
        int temp = min(a[pos].M, t);  
        t -= temp;
        sum += temp * a[pos].tot;
        pos++;
    }cout << fixed << setprecision(2) << sum;
    return 0;
}
    • 5
      @ 2023-5-13 10:50:38

      P1029 金币 Lv.2

      题目描述

      阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N 堆金币，第 i 堆金币的总重量和总价值分别是 mi,vi。阿里巴巴有一个承重量为 T 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

      思路

      对标课上作业。将单位价值求出来，并按照单位价值从大到小排序，加入到背包中。

      结构体：

      struct Coin
{
    double m,v,avg;
}a[101];

      比较：

      bool cmp(Coin a,Coin b)
{
    return a.avg > b.avg;
}

      注意

      金币总重量可能比背包总承重小。

      所以需要加上一步判断。

      for(int i = 0;i < n;i++)
    {
        sum1 += a[i].m;
        sum2 += a[i].v;
    }
    if(sum1 <= t)
    {
        cout << fixed << setprecision(2) << sum2 << endl;
        return 0;
    }

      参考代码：

      #include <iostream>//hetao3097453
#include <algorithm>
#include <iomanip>
using namespace std;
int n;
double t;
double sum1,sum2;
struct Coin
{
    double m,v,avg;
}a[101];
bool cmp(Coin a,Coin b)
{
    return a.avg > b.avg;
}
int main()
{
    cin >> n >> t;
    for(int i = 0;i < n;i++)
    {
        cin >> a[i].m >> a[i].v;
        a[i].avg = a[i].v / a[i].m;
    }
    for(int i = 0;i < n;i++)
    {
        sum1 += a[i].m;
        sum2 += a[i].v;
    }
    if(sum1 <= t)
    {
        cout << fixed << setprecision(2) << sum2 << endl;
        return 0;
    }
    sort(a,a + n,cmp);
    int pos = 0;
    double sum = 0.0;
    while(t > 0)
    {
        double temp = min(a[pos].m,t);
        sum += a[pos].avg * temp;
        t -= temp;
        pos++;
    }
    cout << fixed << setprecision(2) << sum << endl;
    return 0;
}

      hetao3097453

      2023年5月13日

      • @ 2023-5-13 11:00:14

        L10-3

      • @ 2023-10-6 15:16:04

        有没有一种可能？你用#include <bits/stdc++.h> 啊，他更舒服

      • @ 2024-1-22 8:24:55

        Iagree with you.

      • @ 2024-2-4 20:11:19

        我个人更喜欢看一大坨#include，感觉很舒服~~😆@

    • 4
      @ 2023-7-24 12:35:44

      题目作业

      #include <iostream>
#include <algorithm>
using namespace std;
struct Crystal
{
    double volume, power;
    double avg;
};
Crystal a[10005];
bool cmp(Crystal a, Crystal b)
{
    return a.avg > b.avg;
}
int main()
{
    int n;
    double v;
    cin >> n >> v;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].volume >> a[i].power;
        a[i].avg = (a[i].power / a[i].volume)*1.0;
    }
    sort(a+0,a+n,cmp);
    int pos = 0;
    double sum = 0;
    while (v > 0 && pos<=n)
    {
        double minn=min(v,a[pos].volume);
        v-=minn;
        sum+=a[pos].avg*minn;
        pos++;
    }
    printf("%0.2f",sum);
    return 0;
}
    • 3
      @ 2023-5-11 13:51:44
      题目大意
              存在n堆金币，第i堆金币的总重量和总价值是mi, vi。存在承重为T的背包，金币可切割，问最多可以拿走多少价值的金币。

              其中金币总重量可能比背包总承重小

      完整思路
              将每堆金币的单位价值求出来，并按照单位价值从大到小排序，一个个加入到背包中。

              因为金币总重量可能比背包总承重小，之前的代码会出现问题

      
//加入到背包中
int pos = 0;
double sum = 0;
while (c > 0)
{
    double temp = min(a[pos].w, c);
    c -= temp;
    sum += temp * a[pos].p;
    pos++;
}

              若金币总重量小于背包总承重，表示金币a的下标变量pos，会比金币的推数n还要多，数组越界，造成最终的sum与正确结果出现偏差。



      核心代码 
      
//加入到背包中
for (int i = 1; i <= n; ++i)
{
    if (c >= a[i].w)
    {                  //金币的重量小于或等于背包的承重量
        c -= a[i].w;   //装上该堆金币后背包的剩余承重量
        sum += a[i].v; //金币的价值
    }
    else
    {
        sum += c * a[i].p; //如果装不下就分割金币
        break;
    }
}
      • 2
        @ 2024-5-5 19:50:58

        P1029

        -题目回顾-

        阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 𝑁 堆金币，第 𝑖 堆金币的总重量和总价值分别是𝑚𝑖。阿里巴巴有一个承重量为 𝑇 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

        -分析-

        把上一题代码复制过来，在添加 double num = 0,ans = 0;、num += a[i].power;、ans += a[i].volume;、

        if(v >= ans)
    {
        cout << fixed << setprecision(2) << num;
        return 0;
    }

        即可。

        -AC代码-

        请勿一口吞噬哦!否则会被绳之以法封号的哟!(我想了想觉得确实有亿点点一点点不合适)

        #include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
struct Crystal
{
    double volume, power,avg;
};
Crystal a[10005];
bool cmp(Crystal a, Crystal b)
{
    return a.avg > b.avg;
}
int main()
{
    int n, v;
    double num = 0,ans = 0;
    cin >> n >> v;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].volume >> a[i].power;
        a[i].avg = a[i].power / a[i].volume;
        num += a[i].power;
        ans += a[i].volume;
    }
    sort(a,a+n,cmp);
    int pos = 0;
    double sum = 0;
    if(v >= ans)
    {
        cout << fixed << setprecision(2) << num;
        return 0;
    }
    while (v > 0)
    {
        double teap;
        if(v > a[pos].volume)
        {
            teap = a[pos].volume;
        }
        else
        {
            teap = v;
        }
        sum += teap * a[pos].avg,v -= teap;
        pos++;
    }
    cout << fixed << setprecision(2) << sum << endl;
    return 0;
}

        点个赞再走吧，求求了❤️ !

        • 2
          @ 2023-12-12 19:37:45

          P1029 题解

          这道题目比Lv.1多了个条件：如果黄金总重量小于背包承重量，则直接输出黄金总价值。

          那么相应就多出了亿 一些代码

          那我们来看看最后的代码长什么样子

          code

          #include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
struct coin
{
    double m,v,avg;
}a[101];
bool cmp(coin a, coin b)
{
    return a.avg>b.avg;
}
int main()
{
    int n; double t,cnt,cnt2;
    cin>>n>>t;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].m >> a[i].v;
        a[i].avg=a[i].v/a[i].m;
        cnt+=a[i].m;
        cnt2+=a[i].v;
    }
    sort(a, a + n, cmp);
    int pos=0; double sum=0.0;
    if(cnt<=t){
        cout<<fixed<<setprecision(2)<<cnt2;
        return 0;
    }
    while(t > 0){
        double temp = min(a[pos].m,t);
        sum += a[pos].avg * temp;
        t -= temp;
        pos++;
    }
    cout<<fixed<<setprecision(2)<<sum;
    return 0;
}//nice!!

          真香！

          • 1
            @ 2024-6-14 21:12:23

            ~~

            #include <bits/stdc++.h>//by AGOMG(hetao1193656)
using namespace std;
struct Jin{
    double V, M;
    double tot;
}a[1000];
bool cmp(Jin a, Jin b){
    return a.tot > b.tot;
}int main(){
    int n, s = 0;
    float ss = 0;
    double t;
    cin >> n >> t;
    for (int i = 0; i < n; i++){
        cin >> a[i].M >> a[i].V;
        s += a[i].M;
        ss += a[i].V;
        a[i].tot = a[i].V / a[i].M;
    }sort(a, a + n, cmp);
    int pos = 0;
    float sum = 0;
    if(s <= t){cout << fixed << setprecision(2) << ss;return 0;}
    while (t > 0){
        int temp = min(a[pos].M, t);  
        t -= temp;
        sum += temp * a[pos].tot;
        pos++;
    }cout << fixed << setprecision(2) << sum;
    return 0;
}



```~~
            • 1
              @ 2024-4-27 15:34:21 
              #include <bits/stdc++.h>//hetao2646945
using namespace std;
int n;
double t;
double sum1,sum2;
struct Coin
{
    double m,v,avg;
}a[101];
bool cmp(Coin a,Coin b)
{
    return a.avg > b.avg;
}
int main()
{
    cin >> n >> t;
    for(int i = 0;i < n;i++)
    {
        cin >> a[i].m >> a[i].v;
        a[i].avg = a[i].v / a[i].m;
    }
    for(int i = 0;i < n;i++)
    {
        sum1 += a[i].m;
        sum2 += a[i].v;
    }
    if(sum1 <= t)
    {
        cout << fixed << setprecision(2) << sum2 << endl;
        return 0;
    }
    sort(a,a + n,cmp);
    int pos = 0;
    double sum = 0.0;
    while(t > 0)
    {
        double temp = min(a[pos].m,t);
        sum += a[pos].avg * temp;
        t -= temp;
        pos++;
    }
    cout << fixed << setprecision(2) << sum << endl;
    return 0;
}
              • 1
                @ 2024-4-27 15:33:27 
                #include <bits/stdc++.h>//hetao2646945
using namespace std;
int n;
double t;
double sum1,sum2;
struct Coin
{
    double m,v,avg;
}a[101];
bool cmp(Coin a,Coin b)
{
    return a.avg > b.avg;
}
int main()
{
    cin >> n >> t;
    for(int i = 0;i < n;i++)
    {
        cin >> a[i].m >> a[i].v;
        a[i].avg = a[i].v / a[i].m;
    }
    for(int i = 0;i < n;i++)
    {
        sum1 += a[i].m;
        sum2 += a[i].v;
    }
    if(sum1 <= t)
    {
        cout << fixed << setprecision(2) << sum2 << endl;
        return 0;
    }
    sort(a,a + n,cmp);
    int pos = 0;
    double sum = 0.0;
    while(t > 0)
    {
        double temp = min(a[pos].m,t);
        sum += a[pos].avg * temp;
        t -= temp;
        pos++;
    }
    cout << fixed << setprecision(2) << sum << endl;
    return 0;
}
                • 1
                  @ 2023-12-9 18:12:47

                  我觉得吧，大可不必这么麻烦，直接在循环条件处加一个判断就好了

                  #include <bits/stdc++.h>
using namespace std;
struct coin{
    int m,v;
    double average;
}a[105];
int n,t;
double sum;
bool cmp(coin x,coin y){
    return x.average > y.average;
}
int main()
{
    cin >> n >> t;
    for (int i = 1; i <= n; i++){
        cin >> a[i].m >> a[i].v;
        a[i].average = (double)a[i].v / a[i].m;
    }
    sort(a+1,a+n+1,cmp);
    for (int i = 1; (t>0)&&(i<=n); i++){
        sum += a[i].average*min(t,a[i].m);
        t -= min(t,a[i].m);
    }
    printf("%.2lf",sum);
    return 0;
}
                  • 1
                    @ 2023-10-4 13:36:01 
                    #include <bits/stdc++.h>
using namespace std;
int n,pos,valve;
double t,sum,tmp,value;
struct Gold{
    double m,v,avg;
}a[100];
bool cmp(Gold x,Gold y){
    return x.avg>y.avg;
}
int main(){
    cin>>n>>t;
    for(int i=0;i<n;i++){
        cin>>a[i].m>>a[i].v;
        a[i].avg=a[i].v/a[i].m,valve+=a[i].m,value+=a[i].v;
    }
    sort(a,a+n,cmp);
    if(valve<=t){
        printf("%.2lf\n",value);
        return 0;
    }
    while(t>0)tmp=min(t,a[pos].m),t-=tmp,sum+=a[pos++].avg*tmp;
    printf("%.2lf\n",sum);
    return 0;
}
                    • 0
                      @ 2024-2-5 15:18:09

                      和lv1的代码一样也能过

                      #include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
struct Coin{
    double m,v;
    double avg;
};
double n,t,sum;
int pos;
Coin a[100];
bool cmp(Coin a,Coin b){
    return a.avg > b.avg;
}
int main(){
    cin >> n >> t;
    for (int i = 0;i < n;i++){
        cin >> a[i].m >> a[i].v;
        a[i].avg = (a[i].v / a[i].m)*1.0;
    }
    sort(a,a+(int)n,cmp);
    while (t > 0){
        double temp = min(t,a[pos].m);
        t -= temp;
        sum += temp * a[pos].avg;
        pos++;
    }
    cout << fixed << setprecision(2) << sum;
}
                      • -1
                        @ 2023-9-24 12:36:00

                        就在上一题中加个判断就行了，没什么难度。不想做

                        • @ 2023-10-6 15:14:18

                          有圣魔区别，莫看粗来啊。 你知道MOD四森马吗？

                        • @ 2024-2-5 15:18:42

                          也可以不用加判断

                      • 1

                      金币 Lv.2

                      信息

                      ID
                      68
                      时间
                      1000ms
                      内存
                      256MiB
                      难度
                      4
                      标签
                      递交数
                      1905
                      已通过
                      874
                      上传者
                      1. 关于
                      2. 联系我们
                      3. 隐私
                      4. 服务条款
                      5. 版权申诉
                      6. Language
                      7. 兼容模式
                      8. 主题
                      3. Worker 0, 29ms
                      4. Powered by Hydro v4.9.24 Community, Modified by hetao