Codeforces Ronud 892（Div.2）

关于A题我有话说

传送门

题意

给定一个长度为n的数组a，问能否将元素全部放入两个空数组b和c中，使得b和c数组同时满足非空，且c数组中没有任何数是b数组中的数的除数，如果可以输出一种存储方案，不可以就输出-1

思路

当天晚上一开始没有做出来，我一开始的思路是我只要找到一个数除自身外不是任何数的除数,把这个数放到c数组就可以了,感觉这就是正解,但没有通过,应该还是有地方少思考了.
说一下正解思路:
我们可以将数组a进行排序,将最大值放到c数组中,其余的全部放到b数组中,注意,如有多个最大值,全部放在c数组中,最后判断一下b和c的长度即可.

代码

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin>>n;
    std::vector<int > a,b,c;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        a.push_back(x);
    }
    sort(a.begin(),a.end());
    for(int i=0;i<a.size();i++){
        if(a[i]==a[n-1]){
            c.push_back(a[i]);
        }
        else{
            b.push_back(a[i]);
        }
    }
    if(b.size()==0||c.size()==0){
        cout<<-1<<endl;

    }
    else{
        cout<<b.size()<<" "<<c.size()<<endl;
        for(int i=0;i<b.size();i++){
            cout<<b[i]<<" ";
        }
        cout<<endl;
        for(int i=0;i<c.size();i++){
            cout<<c[i]<<" ";
        }
        cout<<endl;
        

    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

关于b题我有话说
传送门

题意

给定n个长度为m的数组,定义美观度为每个数组的最小值之和,对于每个数组,可以将这个数组中最多一个数转移到其他数组当中,输出可能的最大美观度.

思路

因为我们要输出尽可能最大的美观度,所以我们要做的就是将最小值给拿出去,拿到另一个数组,但是这有可能会改变其他数组的最小值,因此我们可以将每个数组中的最小值和次最小值分别存储出来,这样我们把次最小值和最小值排一个序,,除次最小值数组第一个值不要外,拿出最小值数组中第一个元素,将这些数加到一起就是最大美观度

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;

void solve(){
    int n;

    vector<int> a1;
    vector<int> a2;
    ll ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        ll x1 = INF, x2 = INF;
        ll x;
        cin >> x;
        for (ll j = 1, y; j <= x; j++)
        {
            cin >> y;
            if (y < x1)
            {
                x2 = x1;
                x1 = y;
            }
            else if (y >= x1 && y < x2)
            {
                x2 = y;
            }
        }
        a1.push_back(x1), a2.push_back(x2);
    }
    sort(a1.begin(), a1.end());
    sort(a2.begin(), a2.end());

    for (int i = 1; i < n; i++)
    {
        ans += (ll)a2[i];
    }
    ans += (ll)a1[0];
    cout << ans << '\n';
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;

}