zerojudge c561. Bert 愛搗蛋
zerojudge c561. Bert 愛搗蛋
解法大全：
思路的大方向：
１．先選答案，再翻轉
優點：省時間（只要翻轉一次）
缺點：較不直覺，較難寫
答案要先比位數，再比末位數大小
先取位數較多的，再取末位數大的
其方法有：
ａ．排序：
用內建ｓｏｒｔ搭配自寫的ｃｍｐ函式
ｓｏｒｔ語法：
sort(s,s+n,cmp);
重要的是自寫ｃｍｐ函式
自己寫的參考程式碼：
typedef struct obj
{
int len;
string s;
char c;
obj(string a){s=a,len=s.length(),c=s[len-1];}
}OBJ;
int cmp(string s1,string s2)
{
OBJ obja(s1),objb(s2);
if(obja.len==objb.len)
{
if(obja.c==objb.c)return 0;
else if(obja.c<objb.c)return 1;
else return -1;
}
return obja.len-objb.len;
}註：在自訂測資中答案是正確的，但在正式測資時會出現ＮＡ（有時是ＳＥＧＥＲＲＯＲ，有時是答案錯誤）
ｂ．直接選：
/*
DATE:2020/08/20
zerojudge c561
Version:3
status:not complete yet
*/
#include <iostream>
using namespace std;
#include <string>
#define RE_C 1
int cas=0,ti=1;
void check()
{
#ifdef RE_C==1
cout<<cas<<"er"<<ti++<<endl;
#endif
}
typedef struct obj
{
int len;
int last_digit;
int big;
string s;
obj(){big=1;}
void setdigit(){len--;last_digit=s[len-1]-'0';}
}OBJ;
int main()
{
int n=0;
while(cas++,ti=1,cin>>n && n)
{
OBJ *ob=new OBJ [n];
check();
int max_len=0;
for(int i=0;i<n;i++)
{
cin>>ob[i].s;
ob[i].len=ob[i].s.length();
ob[i].last_digit=ob[i].s[ob[i].len-1]-'0';
max_len=max(max_len,ob[i].len);
}
check();
int max_digit=0, cnt=0, flag=1,index=0;
while(flag)
{
cnt=0;
for(int i=0;i<n;i++)
{
if(ob[i].len==max_len)
{
if(max_digit<ob[i].last_digit && ob[i].big)
{
max_digit=ob[i].last_digit;
ob[i].big=1;
index=i;
}
else if(max_digit==ob[i].last_digit && ob[i].big)
{
ob[i].big=1;
index=i;
cnt++;
}
else
{
ob[i].big=0;
}
}
else
{
ob[i].big=0;
}
check();
}
if(cnt==1)
{
flag=0;
cout<<ob[index].s<<endl;
break;
}
else
{
for(int i=0;i<n;i++)
{
ob[i].setdigit();
ob[i].len--;
}
max_len--;
}
}
delete []ob;
}
cout<<"bye"<<endl;
return 0;
}
２．先翻轉，在選答案
優點：較簡單
缺點：較花時間
翻轉方法：
考參考：
https://www.geeksforgeeks.org/reverse-a-string-in-c-cpp-different-methods/
其中方法３（直接返印）是偷雞的方法
Comments
Post a Comment