时间戳

首页 > 解决方案 > 从数组中删除元素，使总和小于或等于特定值。（不是子数组）

c++ - 从数组中删除元素，使总和小于或等于特定值。（不是子数组）

问题描述

我遇到了一个练习问题，其中给了我一个数组，我想从中删除某些元素，以便总和小于给定值，但总和应该接近给定值。

让值是 17 并且给定的数组是 [2, 5, 6 , 8] 然后我可以删除元素 2nd 使得新数组变为 [2, 6, 8] 并且获得的总和为 16。假设数组在递增顺序。

我的尝试：

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;


int main(){
    ll a,b;
    cin>>a>>b;
    vector<ll> v;
    map<ll,vector<ll>> mp;
    ll sum=0;
    for(ll i=0;i<b;i++){
        ll x;
        cin>>x;
        v.push_back(x);
        mp[x].push_back(i);
        sum+=x;
    }
    for(auto x:v) cout << x << " ";
    cout << endl;
  //  cout << sum << endl;
    if(sum<=a){
        cout << b << endl;
        for(ll i=0;i<b;i++){
            cout << i << " ";
        }
        cout << endl;
    }
   else{
       // sort(v.begin(),v.end());
        vector<ll> ind;

            cout << "sum:" << sum<< endl;
            for(auto i=v.begin();i!=v.end();++i){
               cout << "i val:" << (*i) << endl;
                sum = sum - (*i);
                ind.push_back(*mp[*i].begin());
                mp[*i].erase(mp[*i].begin());
                v.erase(i-1,i);
                for(auto x:v) cout << x << " ";
                cout << endl;
                if(sum>a) continue;
                else break;
            }
        cout << sum << endl;

    }
}

标签： c++algorithmoptimization

解决方案

首先确保它已订购。在一个循环中，从数组中的最大数开始，从总和中减去它。与目标值比较，如果总和仍然更大，则删除并返回循环开始，如果不是，则将绝对值（DIF）存储在变量中并重新开始循环。现在您的循环应该查看数组中的下一个最大数字并从总和中减去。假设我们有一个 DIF 值，将当前比较的绝对值与 DIF 进行比较。如果 DIF 更接近，则删除前一个数字，退出循环，就完成了。否则，您将继续，直到找到最佳结果。

推荐阅读