这题先对数组进行排序方便后续操作(每次减去最短长度),利用prev记录每次减去长度,计算最大长度 = 剩余木棍数(n-i) X 本次要切割长度(a[i]-prev)。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<int>a(n);
for(int i = 0;i<n;i++)cin>>a[i];
sort(a.begin(),a.end());
long long max_num=INT_MIN;
long long prev = 0;//记录上一次切割时所使用的最短木棍长度
for(int i = 0;i<n;i++)
{
if(a[i]>prev)
{
//本次切割的总长度 = 剩余木棍数x本次要切割长度
long long cut = (long long)(n-i)*(a[i]-prev);
max_num = max(max_num,cut);
prev=a[i];
}
}
cout<<max_num<<endl;
}
return 0;
}