|
|
ABDE的做法根官方题解一样，就不赘述了，分享一下我C题不太一样的做法。
刚开始也是想用双指针的，但不知道为什么自己把这个方法给否了（脑子晕了），后来想了个更暴力的。
把这n个数分成m组，其中第i组中的数全是i的倍数（一个数可以被分到多个组）这样分完组后所有组的元素数量总共应该是nlogn这个数量级的。
现在这个问题可以等价为，在每组中选一个数，使得选出来的数的极差最小（因为每组选一个数就必定能满足条件了，多选不会更优）
然后我们选择元素数量最少的一组（这组的数量是logn这个数量级的）
我们枚举这组中的每一个数，假设这次是数v,然后对于第i组，暴力遍历找出大于v的最小数a和小于v的最大数b,那这样对于每一组都能确定一个数对(a-v,v-b)，时间复杂度是O(nlogn)的。
那么现在问题就变成了，有(m-1)个数对(x,y),对于每个数对，可以选择把x放入集合A或者把y放入集合B，求max(A)+max(B)的最小值。
这个类型题目的做法可以见Pecco佬的这篇文章，时间复杂度为O(mlogm)
这里把这段代码写一下，想了解原理的可以看上方卡片里的文章
int minsum(vector<pair<int, int>> &V)
{
if (V.empty())
return 0;
sort(V.begin(), V.end());
vector<pair<int, int>> U{V[V.size() - 1]};
for (int i = V.size() - 2; i >= 0; --i)
if (V.second > U.back().second)
U.push_back(V);
int mi = min(U[0].first, U.back().second);
for (int i = 0; i < U.size() - 1; ++i)
mi = min(mi, U.second + U[i + 1].first);
return mi;
}
那这样这题就解决了,最开始处理时我用的是暴力枚举因数，总的时间复杂度为 \Theta(n\sqrt A+n\log^2 n+m\log m\log n) ,其中A是元素最大值，跑了1.6s,勉强AC
附完整代码：
#include<bits/stdc++.h>
using namespace std;
int t,n,m,a,ans;
int minsum(vector<pair<int, int>> &V)
{
if (V.empty())
return 0;
sort(V.begin(), V.end());
vector<pair<int, int>> U{V[V.size() - 1]};
for (int i = V.size() - 2; i >= 0; --i)
if (V.second > U.back().second)
U.push_back(V);
int mi = min(U[0].first, U.back().second);
for (int i = 0; i < U.size() - 1; ++i)
mi = min(mi, U.second + U[i + 1].first);
return mi;
}
int main(){
cin>>t;
while(t--){
cin>>n>>m;
vector<vector<int>>num(m+1);
while(n--){
cin>>a;
int lim=sqrt(a);
for(int i=1;i<=min(lim,m);i++)
if(a%i==0){
num.push_back(a);
if(i*i!=a&&a/i<=m)num[a/i].push_back(a);
}
}
int pos=1;
for(int i=2;i<=m;i++)if(num[pos].size()>num.size())pos=i;
if(num[pos].empty()){
cout<<-1<<endl;
continue;
}
ans=1e9;
for(auto v:num[pos]){
vector<pair<int,int>>temp;
for(int i=1;i<=m;i++)
if(i!=pos){
int l=1e9,r=1e9;
for(auto u:num){
if(u>=v)l=min(l,u-v);
if(u<=v)r=min(r,v-u);
}
temp.push_back({l,r});
}
ans=min(ans,minsum(temp));
}
cout<<ans<<endl;
}
} |
|
发表于 2023-2-1 04:38:25