网资酷

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 105|回复: 1

Codeforces Round #845 (Div. 2) and ByteRace 2023 C

[复制链接]

2

主题

6

帖子

10

积分

新手上路

Rank: 1

积分
10
发表于 2023-2-1 04:38:25 | 显示全部楼层 |阅读模式
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;
        }
}
回复

使用道具 举报

0

主题

3

帖子

4

积分

新手上路

Rank: 1

积分
4
发表于 2025-2-26 19:54:26 | 显示全部楼层
不错 支持下
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|网资酷

GMT+8, 2025-3-15 02:22 , Processed in 0.160893 second(s), 23 queries .

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表