AKK606
2021-12-01 09:49
采纳率: 63.6%
浏览 73

关于如何使用剪枝优化问题

问题遇到的现象和发生背景

如果两个整数是由完全相同的数字组成,且同一种数字的个数也相等,那么这两个整数称为相似数。
例如,12300和20310都是由2个0,1个1,1个2,1个3组成,所以它们是相似数。
而124和120不是相似数,因为组成的数字不同。
120和1200也不是相似数,因为组成的数字虽然相同,但0的个数不相等,120中有1个0,而1200中有2个0
多个整数也可以相似。
给出N个不同的正整数,求最多有多少个数相似。例如,如果最多有3个数相似,则输出3,最多有2个数相似,输出2.如果所有数均不相似,则输出1。

这个问题如何在大量数据下进行剪枝优化

问题相关代码,请勿粘贴截图
#include <bits/stdc++.h>
using namespace std;
int a[1000005][15], m[1000005], s[1000005];
int k = 0;
int num(int x) {
    if (s[x] != 0)
        return s[x];
    int cnt = 0;
    while (x != 0) {
        cnt++;
        x /= 10;
    }
    return s[x] = cnt;
}
void fun(int x) {
    int i = x;
    while (x != 0) {
        k = x % 10;
        a[i][k]++;
        x /= 10;
    }
}
bool check(int x, int y) {
    for (int i = 0; i <= 9; i++) {
        if ((a[x][i]) != (a[y][i]))
            return 0;
    }
    return 1;
}
int main() {
    int c, d, s = 0, maxn = 0;
    cin >> c;
    for (int i = 1; i <= c; i++) {
        cin >> m[i];
        fun(m[i]);
    }
    sort(m + 1, m + 1 + c);
    for (int i = 1; i <= c; i++) {
        s = 1;
        for (int j = i + 1; j <= c; j++) {
            if (num(m[j]) > num(m[i]))
                break;
            if (check(m[i], m[j]) == 1) {
                s++;
                if (s >= maxn)
                    maxn = s;
            }
        }
    }
    if (maxn == 0)
        cout << -1;
    else
        cout << maxn;
    return 0;
}

运行结果及报错内容

对于小数据而言比较容易处理,但是数据大了之后就会用时很长

我的解答思路和尝试过的方法
我想要达到的结果
  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

2条回答 默认 最新

相关推荐 更多相似问题