[ABC270D] Stones

Demons_Killer · 2023-08-25 10:54:08 · 题解

解题思路：

很简单的一道贪心模拟题。

每次都取最大的石头，n 不够就取少一点的石头，取到不能取为止。记得要先排一个序，让石头序列保持单调递增，这样才能尽可能多的取石头。

把每次取的石头数量加起来，就得到了最终答案。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+10;
int n,k;
int a[N];
int f[N];
int ans;
signed main(){
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+k);
    while(n>=a[1]){
        for(int i=k;i>=1;i--){
            if(n>=a[i]){
                ans+=a[i];
                n-=a[i];
                break;
            }
        }
        for(int i=k;i>=1;i--){
            if(n>=a[i]){
                n-=a[i];
                break;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}