GHOJ 277 吃鱼

题目描述

　　小花爱吃鱼，这是全世界都知道的事情。它的好朋友编程兔给它准备了很多的零食，每一样都是小花喜欢的。当然了，里面最多的肯定是鱼。某一天编程兔给小花准备了两种鱼，一种鱼的重量是1，另一种鱼的重量是2，重量为1的鱼有不同的美味值，重量为2的鱼也有不同的美味值。现在假设小花的胃口最多能吃下不超过重量为v的鱼，小花希望吃掉的鱼的美味值总和最大。

输入输出格式

输入格式

　　第一行是两个正整数n和v，n表示鱼的数量，v表示小花的胃口。

　　接下来n行，每行两个正整数，第一个正整数表示鱼的重量（只有1和2两种可能），另一个正整数表示这条的美味值。

 

输出格式

　　一行，一个整数，表示小花能得到的最大美味值总和。

输入输出样例

输入样例

3 2

1 2

2 7

1 3

输出样例

7

说明

样例说明

　　小花选择了第2条鱼吃，美味值是7。

数据规模

　　对于60%的数据，1≤n≤2000。

　　对于100%的数据，1≤n≤30000，1≤v≤60000，每条鱼的美味值不超过10000。

题解　　

　　这道题其实是一道暴力枚举题，但是有一种贪心做法还是可取的。

　　下面把重量为1的鱼称为鱼1，重量为2的鱼称为鱼2.

　　首先尽可能吃价值高的鱼1，吃完还没饱再尽可能吃价值高的鱼2.

　　此时尝试用剩下的鱼2去换鱼1，取最优即可。

　　最后要判断是否还有剩余空间。

#include <iostream>
#include <cstdio>
#include <algorithm>

#define MAX_N 30000
#define MAX_M 60000

using namespace std;

int n;
int m;
struct Fish
{
    int w;
    int v;
    inline bool operator < (const Fish & x) const
    {
        if(w != x.w) return w < x.w;
        return v > x.v;
    }
};
Fish a[MAX_N + 5];
int ans;

int main()
{
    scanf("%d%d", &n, &m);
    int mid = 0;
    for(register int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &a[i].w, &a[i].v);
        if(a[i].w & 1) ++mid;
    }
    sort(a + 1, a + n + 1);
    int i = 0, j = mid;
    while(i < mid && i < m)
    {
        ans += a[++i].v;
    }
    while(j < n && i + (j - mid + 1 << 1) <= m)
    {
        ans += a[++j].v;
    }
    while(i >= 2 && j < n && a[i].v + a[i - 1].v <= a[j + 1].v)
    {
        ans += a[++j].v - a[i--].v - a[i--].v;
    }
    if(i < mid && i + (j - mid << 1) < m)
    {
        ans += a[++i].v;
    }
    printf("%d", ans);
    return 0;
}

　　下面也附上暴力程序。只需要运用前缀和。

#include <iostream>
#include <cstdio>
#include <algorithm>

#define MAX_N 30000
#define MAX_M 60000

using namespace std;

int n;
int m;
struct Fish
{
    int w;
    int v;
    inline bool operator < (const Fish & x) const
    {
        if(w != x.w) return w < x.w;
        return v > x.v;
    }
};
Fish a[MAX_N + 5];
int ans;

int main()
{
    scanf("%d%d", &n, &m);
    int mid = 0;
    for(register int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &a[i].w, &a[i].v);
        if(a[i].w & 1) ++mid;
    }
    sort(a + 1, a + n + 1);
    for(register int i = 1; i <= n; ++i)
    {
        a[i].v += a[i - 1].v;
    }
    m = min(m, mid + (n - mid << 1));
    for(register int i = 0; i <= m; i += 2)
    {
        if((m - i) <= mid && mid + (i >> 1) <= n)
        {
            ans = max(ans, a[m - i].v + a[mid + (i >> 1)].v - a[mid].v);
        }
    }
    printf("%d", ans);
    return 0;
}