#include <iostream> #includ<algorithm> #define ll long long using namespace std; ll t,n,m,sum; int a[10005]; void f() { for(int i=1;i<=n-1;i++){ for(int j=1;j<=n-i;j++){ if(a[j]>a[j+1]){ int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } ll cnt=0; if(sum>m){ for(int i=n;i>=1;i--) { cnt++; ll op=sum-m; if(op<=a[i]+1e4) break; sum=sum-a[i]-1e4; } }else if(sum<m){ for(int i=1;i<=n;i++) { ll op=m-sum; cnt++; if(op<=a[i]+1e4) break; sum=sum-a[i]+1e4; } } cout << cnt << endl; }

int main() { cin >> t; while(t--){ cin >> n >> m; sum = 0; for(int i=1;i<=n;i++){ cin >> a[i]; sum+=a[i]; } if(sum==m) { cout << 0 << endl; continue; } f(); } return 0; }

#include<stdio.h> int main() { int n; scanf("%d",&n); while(n--) { int a,b,sum=0; scanf("%d%d",&a,&b); int arr[100000]={0}; for(int i=1;i<=a;i++) { scanf("%d",&arr[i]); sum+=arr[i]; } for(int i=1;i<=a;i++) { for(int j=1;j<=a-i;j++) { if(arr[j]>arr[j+1]) { int y=arr[j]; arr[j]=arr[j+1]; arr[j+1]=y; } } } int t=sum-b; int m=0; if(t>0) { for(int i=a;i>=0;i--) { if(t<=0) { break; } else { m++; t=t-arr[i]-10000; } } } else if(t<0) { for(int i=1;i<=a;i++) { if(t>=0) { break; } else { m++; t=t-arr[i]+10000; } } } printf("%d\n",m); } return 0; }

贪心+模拟

令数组总和为$num$,显然，当$sum > num$时， 我们需要让原数组元素增大。$sum<num$时，我们需要减小原数组元素。 想要用最少的次数来修改，显然修改最值最优。 两种情况分别讨论，当$sum>num$,我们尽量修改原数组中较小的值，反之则修改较大的。排序后模拟即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200005];
void solve()
{
	int n,m;
  cin >> n >>m;
  int sum=0;
  for(int i=1;i<=n;i++)
  {
    cin >> a[i];
    sum+=a[i];求数组总和
  }
  for(int i=1;i<=n;i++)//冒泡排序
  {
    for(int j=1;j<=n-i;j++)
    {
        if(a[j]>a[j+1])
        {
            int opp=a[j];
            a[j]=a[j+1];
            a[j+1]=opp;
        }
    }
  }
  int ans=0;
  if(sum<m)
  {
       for(int i=1;i<=n;i++)
       {
        ans++;
        int op=sum-a[i];
        int num=m-op;
        if(num<=1e4&&num>=-1e4)//最后一次修改
        {
          a[i]=num;
          break;
        }
        else
        {
          sum=sum-a[i];
          a[i]=1e4;//贪心
          sum=sum+a[i];
        }
       }
  }
  else if(sum>m)
  {
      for(int i=n;i>=1;i--)/步骤同上
      {
        ans++;
        int op=sum-a[i];
        int num=m-op;
        if(num<=1e4&&num>=-1e4)
        {
          a[i]=num;
          break;
        }
        else
        {
          sum-=a[i];
          a[i]=-1e4;
          sum=sum+a[i];
        }
      }
  }
  cout <<ans<<'\n';
}
signed main()
{
	int t;
	cin >> t;
	while(t -- )
	{
		solve();
	}
	 
}