求调

P1478 陶陶摘苹果（升级版）

Luansuan @ 2024-11-16 02:11:49

#include<stdio.h>
#include<stdlib.h>
#define N 2

int main()
{
    int n,s,a,b,h;

    scanf("%d %d %d %d",&n,&s,&a,&b);
    h=a+b;

    int max,k,t,i,j,x[n][N];

    for(i=0;i<n;i++){
        for(j=0;j<N;j++){
            scanf("%d",&x[i][j]);
        }
    }
    //高度排列
    for(k=0;k<n-1;k++){
        for(i=0;i<n-k-1;i++){
            if(x[i][0]>x[i+1][0]){
                for(j=0;j<N;j++){
                    t=x[i][j];
                    x[i][j]=x[i+1][j];
                    x[i+1][j]=t;
                }
            }
        }
    }
    for(i=0;i<n;i++){
        if(x[i][0]>h){
            max=i;
            break;
        }
    }
    //力气排列
    for(k=0;k<max-1;k++){
        for(i=0;i<max-k-1;i++){
            if(x[i][1]>x[i+1][1]){
                for(j=0;j<N;j++){
                    t=x[i][j];
                    x[i][j]=x[i+1][j];
                    x[i+1][j]=t;
                }    
            }
        }
    }
    int cnt=0;
    for(i=0;i<n;i++){
        if(s>=x[i][1]){
            s-=x[i][1];
            cnt++;
        }else break;
    }

    printf("%d\n",cnt);

    system("pause");
    return 0;
}

by Arabidopsis @ 2024-11-23 09:30:55

贪心题，按照需要的力气进行排序，之后优先选择需要力气小的即可。

AC代码奉上：

#include <iostream>
#include <algorithm>

using namespace std;

struct Apple
{
    int height;
    int strength;
}apples[5001];

bool cmp(Apple left, Apple right) 
{
    return left.strength < right.strength;
}

int main()
{
    int n, s, a, b, ans = 0;
    cin >> n >> s >> a >> b;

    auto maxh = a + b;

    for (size_t i = 0; i < n; i++)
    {
        cin >> apples[i].height >> apples[i].strength;
    }

    sort(apples, apples + n, cmp);

    for (size_t i = 0; i < n; i++)
    {
        if (maxh >= apples[i].height && s >= apples[i].strength) 
        {
            s -= apples[i].strength;
            ans++;
        }

        if (s < 0)break;
    }

    cout << ans;

    return 0;
}