3530. 和你在一起

题面 统计数据 讨论
Fifnmar
2 年，5 月前

这是一道经典的字符串题，虽然是以数字样式给出的。

首先，我们来观察只有两个字符串 $a$ 和 $b$ 的情形。因为 $a$ 和 $b$ 的长度可能不相同，根据分析我们可以看出应该这样比较：
$$let\,\,a\,\,be\:\:321\;\;and\;\;b\;\;be\;\;42$$
$$we\;\;have$$
$$a+b=32142<b+a=42321$$
可见正确的比较姿势是把两个字符串续起来再比较。

然后观察有更多的字符串的情形。假设我们有 $n$ 个字符串的集合 $A$，那么 $\exists \; x \in A,\;s.t.\;\forall\;y \in A,\;y\neq x,\;x\geq y$ 。这个 $x$ 应该被放在第一位，因为如果有另一个字符串 $y$ 被放在第一位，那么一定可以在第二从位放 $x$ 且使得 $y+x\leq x+y$，不能满足需求。

综上，我们发现只要用「把两个字符串加进来比较」的方法把字符串排序就好了。如果是直接比较，可能会出错。这个前面的大佬们已经解释并举反例啦！

下面是程序：

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> n;
    string *nums = new string[n], *ed = nums + n;
    for (string *i = nums; i != ed; ++i)
        cin >> *i;
    sort(nums, ed, [](string &a, string &b) { return b + a < a + b; });
    for (string *i = nums; i != ed; ++i)
        cout << *i;
    cout << '\n';
}
回复
Fifnmar
2 年，1 月前

偶然回来看到这个，发现自己有五个赞……

有点愧对大家，我贴的这个程序不太好……

一般不建议用裸的 new 和 delete。那段时间我写这样的代码，不好。如果还有后来者看到这份代码，用 vector 代替吧。

回复
Fifnmar
2 年，5 月前

EOJ 的 Markdown 也太丑了

回复
Fifnmar
2 年，1 月前 
int main() {
    unsigned n; cin >> n;
        vector<string> nums(n);
        for (auto &i : nums)
            cin >> i;
        sort(nums.begin(), nums.end(), [](string const& a, string const& b) { return b + a < a + b; });
        for (auto const& i : nums)
            cout << i;
}
回复
Patchouli
2 年，10 月前

测试用例有问题，举个例子

3
78 71 7
根据AC代码跑出来的结果是78717，而很明显，答案应该是78771
希望可以增加这些测点吧

回复
LzQuarter
3 年，6 月前 
#include<iostream>
#include<algorithm>
using namespace std;
int fun(string a, string b){
    if(a.length() == b.length()){
        //do nothing
    }
    else if(a.length() > b.length()){
        int dlen = a.length() - b.length();
        for(int i = 0; i < dlen; i++){
            b += a[i];
        }
    }
    else{
        int dlen = b.length() - a.length();
        for(int i = 0; i < dlen; i++){
            a += b[i];
        }
    }
    return a > b;
}
int main(){
    int n;
    string arr[30];
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    sort(arr, arr + n, fun);
    for(int i = 0; i < n; i++){
        cout << arr[i];
    }
    return 0;
}
回复
Akaricyan
2 年，5 月前

这是正解！
2
492 49
问题在于这种例子。

回复
站在岸上的yu
2 年前

bool EOJ_3530_cmp(string a, string b)
{
return a + b > b + a; //a在前比较大时，把a放在b前面
}
int main()
{
int N;
cin >> N;
vector vi;

string temp;
for (int i = 0; i < N; i++)
{
    cin >> temp;
    vi.push_back(temp);
}
sort(vi.begin(), vi.end(), EOJ_3530_cmp);

for (int i = 0; i < N; i++)
    cout << vi[i];
cout << endl;
return 0;

}

回复
PGFIVE5
3 年，5 月前 
n = int(input())
x=list(input().split())
x.sort(reverse=True)
for m in x:
    print(m,end='')

这样都能AC是不是说明数据有问题

回复
告白于荆州
3 年，5 月前

测试样例似乎并没有考虑全面，这道题肯定不是简单的排序再输出

回复
训练专用账号
5 月前

确实有问题

回复
柴柴柴拆柴柴
2 年，4 月前

水题

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>

struct num{
    int mynum;
};
typedef struct num NUM;

int mycoup(const void * p1,const void * p2);
int min(int a,int b);

int main(void)
{
    int cases,i;
    NUM *inputlst;

    scanf("%d",&cases);
    inputlst=(NUM*)malloc(cases*sizeof(NUM));

    for(i=0;i<cases;i++)
        scanf("%d",&inputlst[i].mynum);

    qsort(inputlst,cases,sizeof(NUM),mycoup);
    for(i=0;i<cases;i++)
    {
        printf("%d",inputlst[i].mynum);
        if(i==cases-1)
            printf("\n");
    }

    free(inputlst);
    return 0;
}

int mycoup(const void * p1,const void * p2)
{
    const NUM * a1=(const NUM *)p1;
    const NUM * a2=(const NUM *)p2;
    char temp1[10001],temp2[10001];
    int i,len1,len2;

    sprintf(temp1,"%d",a1->mynum);
    sprintf(temp2,"%d",a2->mynum);

    len1=strlen(temp1);
    len2=strlen(temp2);

    for(i=0;i<min(len1,len2);i++)
    {
        if(temp1[i]>temp2[i])
            return -1;
        else if(temp1[i]<temp2[i])
            return 1;
    }
    return 0;
}

int min(int a,int b)
{
    if(a<b)
        return a;
    else
        return b;
}
回复
xhliao
3 年，1 月前

include

include

include

using namespace std;
typedef struct{
char num[10];
}ST;
ST s[20];

bool cmp(ST a,ST b){
return strcmp(a.num,b.num)>0;
}

int main(){
int n,i;
cin>>n;
for(i=0; i>s[i].num;
}
sort(s,s+n,cmp);
for(i=0; i<n; i++){
cout<<s[i].num;
}
return 0;
}

回复
madmax
1 年，10 月前

好像有点问题，数据：912 9 78
正解：991278
AC输出：912978

回复
万古星空悬皓月
3 年，1 月前

input()
print(‘’.join(sorted(input().split(‘ ‘), reverse=True)))
可耻不= =

回复
WhiteLi
2 年，3 月前

什么数据 这么水

回复
aspen138
5 月前

甚至没有考虑前导零的情况也能过。。。

回复
liupeng19970119
3 年，1 月前

include

using namespace std;
int main()
{
int n;
int a[20] = {};
int b[20] = {};
int c[20] = {};
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < n; i++)
{
if (a[i] >1000){ b[i] = a[i] / 1000; }
else if (a[i] >100 && a[i] < 1000)
{
b[i] = a[i] / 100;
}

    else if (a[i] >= 10 && a[i] <= 100)
    {
        b[i] = a[i] / 10;
    }
    else
        b[i] = a[i] % 10;
}
int temp;
for (int i = 0; i < n; i++)
{
    for (int j = i; j < n; j++)
    {
        if (b[j]>b[i])
        { 
            temp = b[i]; b[i] = b[j]; b[j] = temp;
            temp = a[i]; a[i] = a[j]; a[j] = temp;
        }
        if (b[j]==b[i])
        {
            if (a[j]<10)
            {
                temp = b[i]; b[i] = b[j]; b[j] = temp;
                temp = a[i]; a[i] = a[j]; a[j] = temp;
            }
            if (a[j]>100 && a[j] < 1000)
            {
                if (a[i]>1000){
                    if (a[j] > (a[i] / 10))
                    {
                        temp = b[i]; b[i] = b[j]; b[j] = temp;
                        temp = a[i]; a[i] = a[j]; a[j] = temp;
                    }

                }
            }
            if (a[i]>100 && a[i] < 1000)
            {
                if (a[j]>1000){
                    if (a[j] / 10 > (a[i]))
                    {
                        temp = b[i]; b[i] = b[j]; b[j] = temp;
                        temp = a[i]; a[i] = a[j]; a[j] = temp;
                    }

                }
            }
            if ((a[j] > 1000 && a[i] > 1000) ||( (a[j] < 1000 && a[j]>100) && (a[i] < 1000 && a[i]>100)))
            {
                if (a[j]>a[i])
                {
                    temp = b[i]; b[i] = b[j]; b[j] = temp;
                    temp = a[i]; a[i] = a[j]; a[j] = temp;
                }
            }
        }

    }
    c[i] = a[i];
}
for (int i = 0; i < n; i++){ cout << c[i]; }

}

回复
YZAZJL
2 年，2 月前

include

include

using namespace std;
typedef struct Data{
int num;
int first;
int second;
int third;
int forth;
}data;
bool cmp(Data a, Data b){
if(a.first == b.first){
if(a.second == b.second){
if(a.third == b.third){
return a.forth > b.forth;
}
return a.third > b.third;
}
return a.second > b.second;
}
return a.first > b.first;
}
int main()
{
int n;
cin >> n;
int i;
Data data[n];
for(i = 0; i < n; i++){
int number;
cin >> number;
data[i].num = number;
int fir, sed, thid, fort;
fir = number / 1000;
number = number % 1000;
sed = number / 100;
number = number % 100;
thid = number / 10;
fort = number % 10;
while(fir == 0){
fir = sed;
sed = thid;
thid = fort;
fort = fort;
}
data[i].first = fir;
data[i].second = sed;
data[i].third = thid;
data[i].forth = fort;
}
sort(data, data + n, cmp);
for(i = 0; i < n; i++){
cout << data[i].num;
}
cout << endl;
return 0;
}

回复
ChengChao
1 年，2 月前

运用sort来比较字符串vector，cmp函数为链接字符串串后 a+b>b+a;

include

using namespace std;

bool cmp(string a,string b){
return a+b>b+a;
}

int main(){
int n;
cin>>n;
vector vec;
string input;
for(int i=0;i>input;
vec.push_back(input);
}
sort(vec.begin(),vec.end(),cmp);
for(vector::iterator it=vec.begin();it!=vec.end();it++)
cout<< *it;
return 0;
}

回复
你当前正在回复 博客/题目
存在问题！

服务

首页 反馈 Polygon Wiki

开源

Github eJudge

关于我们

团队: @ultmaster, @zerol, @kblack.
联系方式: acmsupport@admin.ecnu.edu.cn