关于#c++#的问题：c++贪心题怎么改

Question

#include<bits/stdc++.h>
using namespace std;
long long a[114514];
int main() {
    long long w,n;
    long long z=0;
    cin>>w>>n;
    for (long long i=1; i<=n; i++) {
        cin >> a[i];
    }
    long long m=n;
    sort(a+1,a+1+n);
    for (long long i=1; i<=n; i++) {
        for (long long j=m; j>i; j--) {
            if (a[i]+a[j]<=w) {
                z++;
                m=j-1;
                break;
            }
        }
    }
    z=z+(n-z*2);
    cout<<z;
    return 0;
}

Answer 1

我忽略了Pi>w的情况，代码如下

#include<bits/stdc++.h>
using namespace std;
long long a[114514];
long long asd=0;
long long w,n;
long long z=0;
int main() {
    cin>>w>>n;
    for (long long i=1; i<=n; i++) {
        cin >> a[i];
    }
    long long m=n;
    sort(a+1,a+1+n);
    for (int i=1; i<=n; i++) {
            if (a[i]>w) {
                asd++;
            }
    }
    for (long long i=1; i<=n; i++) {
        for (long long j=m; j>i; j--) {
            if (a[i]+a[j]<=w) {
                z++;
                m=j-1;
                break;
            }
            
        }
    }
    z=z+(n-z*2);
    cout<<z-asd;
    return 0;
}