360：序列重组

题目描述：

360公司 2020秋招 技术综合C卷在线考试
编程题 | 30.0分2/2
序列重组
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
在一个古老的国度，这个国家的人并不懂得进位，但是对取模情有独钟，因此诞生了一个经典的问题，给出两个在m进制下含有n位的数字，你可以分别将这两个数各位上的数字重新排列，然后将两个数按位对应相加并分别对m取模，这样显然可以得到一个新的m进制下的n位数(可能存在前导0)，但是这个结果是不唯一的，问题来了，按照这样的操作，能够得到的最大的m进制下的数字是多少呢。

输入
输入第一行包含两个正整数n,m分别表示数字含有n位，和在m进制下。（n，m≤100000）

输入第二行和第三行分别包含n个整数，中间用空格隔开，每个整数都在0到m-1之间。每行第i个数表示的是当前数第i位上的数字。

输出
输出包含n个数字，中间用空格隔开，表示得到的最大的数字，从高位到低位输出，如6在2进制下输出3位的结果是1 1 0。


样例输入
5 5
4 4 1 1 1 
4 3 0 1 2
样例输出
4 4 3 3 2

提示
4 4 1 1 1 →1 4 1 4 1
4 3 0 1 2 →3 0 2 4 1（重排序列不唯一，数位相加后的数字为 4 4 3 8 2，对5取模即可 ）

代码：

作者：Dvelpro
链接：https://www.nowcoder.com/discuss/224600?type=0&order=0&pos=17&page=1
来源：牛客网
直接暴力解，先排序，然后贪心，这题复杂度太假了，最后偶尔能过100% 有点卡常

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t1[100010],t2[100010];
int tmp[100010],tot=0;
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    multiset<int> s1,s2;
    for(int i=1;i<=n;i++){
        int tmp;scanf("%d",&tmp);s1.insert(tmp);
    }
    for(int i=1;i<=n;i++){
        int tmp;scanf("%d",&tmp);s2.insert(tmp);
    }
    for(int i=m-1;i>=0;i--){
        tot=0;
        for(multiset<int>::iterator j=s1.begin();j!=s1.end();++j){
            if(s2.find((i-(*j)+m)%m)!=s2.end()){
                tmp[tot++]=*j;
                s2.erase(s2.find((i-(*j)+m)%m));
                printf("%d ",i);
            }
        }
        for(int j=0;j<tot;j++){
            s1.erase(s1.find(tmp[j]));
        }
    }
 
 
    return 0;
}

代码2：

原文链接：https://blog.csdn.net/qq_18310041/article/details/99656445

import copy
# m进制
m = 5
n = 5
line = [[4,4,1,1,1],[4,3,0,1,2]]
 
res = []
count_0 = []
count_1 = copy.deepcopy(line[1])
 
for i in range(n):
    count_0.append(m - 1 - line[0][i])
for i in range(n):
    if line[1][i] in count_0:
        res.append(m-1)
        count_0.remove(line[1][i])
        count_1.remove(line[1][i])
count_0.sort(reverse= True)
count_1.sort(reverse= False)
for i in range(len(count_0)):
    count_0[i] = m - 1 - count_0[i]
    t = count_0[i] + count_1[i]
    if t > m-1:
        t =t - m
        res.append(t)
    else:
        res.append(t)
res.sort(reverse=True)
print(res)

360：序列重组

相关推荐