3530. 和你在一起

Deuchie

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

首先,我们来观察只有两个字符串 $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';
}
Deuchie

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

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

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

Deuchie

EOJ 的 Markdown 也太丑了

Deuchie
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

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

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

LzQuarter
#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
492 49
问题在于这种例子。

万古星空悬皓月

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

WhiteLi

什么数据 这么水

liupeng19970119

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

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;
}

PGFIVE5
n = int(input())
x=list(input().split())
x.sort(reverse=True)
for m in x:
    print(m,end='')

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

告白于荆州

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

站在岸上的yu

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;

}

柴柴柴拆柴柴

水题

#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

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

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

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