The Great Mixing CF788C

从序列中找一些数，使平均数>=m,问最少取几个数》

  每个数 - m , 题目即求 和>=0 最少取多少数？ 背包问题

#include <iostream>
#include<algorithm> 
#include <cstring>
#define IOS std::ios::sync_with_stdio(0)
using namespace std;
 const int M =4e6+3;
  const int D= 2e6;
  
 
 int f[M],a[M],m,n;
 
 void solve(){
 	 memset(f,63,sizeof f);
 	int i,j;
 	cin>>m>>n;
 	for(i=1;i<=n;i++) scanf("%d",&a[i]),a[i]-=m;
 	sort(a+1,a+1+n);
 	int len=unique(a+1,a+1+n)-a-1;
   
 	for(i=1;i<=len;i++){
 		f[a[i]+D]=1;
 		if(a[i]<0){
 			for(j=5e5;j>=-5e5;j--)
		 	 	 f[j+D]=min(1+f[j-a[i]+D],f[j+D]);
 		}
	 	else{
 	 		for(j=-5e5;j<=5e5;j++)
 	 			f[j+D]=min(1+f[j-a[i]+D],f[j+D]);
		}
 	}
 	
 	if(f[D]<=1e9)
		cout<< f[D] <<endl;
 	else 
 		cout<<-1<<endl;
 }
 signed main(){
     IOS;
     solve();
 }