玲珑杯 1125 - 咸鱼商店

た入场券 2022-06-15 09:41 160阅读 0赞

你现在在咸鱼商店，你有M元钱。咸鱼商店有N个物品，每个物品有两个属性，一个是他的价格S\[i\]，另外一个是他的价值V\[i\]。现在你想买一些物品，使得这些物品的价值和大于等于K，并且使得其中价值最低的商品的价值尽量高。请你输出这个最大价值。

INPUT

第一行三个整数N,M,K。接下来N行，每行两个整数S和V，分别表示价格和价值。满足：1 <= N, M, S <= 10^3, 0 <= V, K <= 10^6

OUTPUT

输出价值最低的商品能够达到的最大价值。如果无解，输出-1

SAMPLE INPUT

3 10 11 210 15 5

SAMPLE OUTPUT

5

SOLUTION

[玲珑杯”ACM比赛 Round \#15][ACM_ Round _15]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int n,m,k;
    struct node
    {
        int s,v;
        bool operator < (const node &x) const{
            if(x.v==v)
                return s<x.s;
            return v>x.v;
        }
    } f[1005];
    int main()
    {
        while(~scanf("%d %d %d",&n,&m,&k))
        {
            for(int i=0;i<n;i++)
                scanf("%d %d",&f[i].s,&f[i].v);
            sort(f,f+n);
            int ok=-1;
            int ans=0,anv=0;
            for(int i=0;i<n;i++)
            {
                if(ans+f[i].s<=m)
                {
                    if(anv+f[i].v>=k)
                    {
                        printf("%d\n",anv+f[i].v);
                        ok=1;
                        break;
                    }
                    else
                    {
                        ans=ans+f[i].s;
                        anv=anv+f[i].v;
                    }
                }
            }
            if(ok==-1)
                printf("-1\n");
        }
        return 0;
    }

[ACM_ Round _15]: http://www.ifrog.cc/acm/solution/20

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

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

相关阅读

相关 1125day7

1.SVM算法的优缺点优点：可以优先解决高维特征的分类和回归问题无需依赖全体样本，只依赖支持向量有大量的核技巧可以使用，从而应对线性不可分问题适合样本量

分手后的思念是犯贱/ 2022年12月24日 04:58/ 0 赞/ 158 阅读

相关最短路poj 1125

题目：[poj1125Stockbroker Grapevine][poj1125_Stockbroker Grapevine] 题意：此题题意远比题目难

刺骨的言语ヽ痛彻心扉/ 2022年08月27日 15:54/ 0 赞/ 166 阅读

相关玲珑杯 1125 - 咸鱼商店

你现在在咸鱼商店，你有M元钱。咸鱼商店有N个物品，每个物品有两个属性，一个是他的价格S\[i\]，另外一个是他的价值V\[i\]。现在你想买一些物品，使得这些物品的价值和大于等

た入场券/ 2022年06月15日 09:41/ 0 赞/ 161 阅读

相关玲珑杯----C 咸鱼魔法记

给你一个01串，我们定义这个串的咸鱼值，是最长的全1串。现在你最多可以使用K次咸鱼魔法，每次魔法，你可以使得一个位置翻转（0变成1,1变成0）。问你这个串的咸鱼值最多是多少。

我不是女神ヾ/ 2022年06月15日 09:24/ 0 赞/ 174 阅读

相关玲珑杯1141-fft计数

题目链接：[传送门][Link 1] 1141 - 喵哈哈村的智慧大师丶).妩钶取玳°月 Time Limit：1s Memory Limit：256MByte

￡神魔★判官ぃ/ 2022年06月13日 02:50/ 0 赞/ 151 阅读

相关 POJ 1125, Stockbroker Grapevine

Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 10318 Accepted: 5591

淡淡的烟草味﹌/ 2021年12月22日 06:45/ 0 赞/ 186 阅读

相关玲珑杯#20 C 漆黑的太阳——莫队

题目：[https://www.ifrog.cc/acm/problem/1155][https_www.ifrog.cc_acm_problem_1155] 题解：[htt

青旅半醒/ 2021年12月07日 13:09/ 0 赞/ 215 阅读

相关 poj 1125 Floyd简单

这是求所有节点间最短路径的题。果断用floyd，三个for循环就OK！如果不懂floyd，[请看这里][Link 1]。题意有点绕。。。我不知道怎么描述，看了discuss里面

叁歲伎倆/ 2021年11月29日 17:36/ 0 赞/ 267 阅读

相关 poj 1125 FLoyd

题意：让你找一个点，从这个点向其它点传递信息所要的时间最短。输出这个点得编号，和最晚收到信息的人所需时间。算法： 1.Dijkstra算法一次只能求单源最短路径，而

淩亂°似流年/ 2021年11月02日 14:26/ 0 赞/ 230 阅读

相关【玲珑杯R7 D】Pick Up Coins

Time Limit：10s Memory Limit：1024MByte Submissions：335Solved：126 DESCRIPTION There ar

客官°小女子只卖身不卖艺/ 2021年10月26日 17:16/ 0 赞/ 349 阅读