图片说明
图片说明

  • 题意：
  • 给出每条鱼烤制的时间，抓捕每条鱼的时间是相同的，问你最少花费多少时间才能将所有的鱼抓完并烤完。
  • 题解：
  • 贪心策略，就是要让自己的空闲时间越小越好，处理好每个烤鱼的时间，排序完后直接相加就好了，确实是想复杂了，贪心策略越简练越容易a，想麻烦可就事大了。
  • 代码：
    #include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
  ll x,k;
}a[100010];
bool cmp(node p1,node p2)
{
  return p1.k < p2.k;
}
ll min(ll x,ll y)
{
  return x<y?x:y;
}
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
      ll n,m;
      scanf("%lld %lld",&n,&m);
      ll now = n-1;
      for(int i=1;i<=n;i++)
      {
          scanf("%lld",&a[i].x);
          int d = a[i].x/m;
          d = min(d,now);
          now -= d;
          a[i].k = a[i].x - d*m;
      }
      sort(a+1,a+1+n,cmp);
      ll ans = n*m;
      for(int i=1;i<=n-now;i++)
      {
          ans += a[i].k;
      }
      cout<<ans<<endl;
  }
  return 0;
}