当前位置:网站首页>#PAT#day10
#PAT#day10
2022-07-06 02:43:00 【Mianmian fist beats the back 5r/ time】
List of articles
Introduction (2)—— The algorithm is preliminary (4.4 greedy )
1067 Sort with Swap(0, i)
My code (19/25)
#include<stdio.h>
//#include<algorithm>
//using namespace std;
int a[100010];
void swap(int &a,int &b){
int temp=a;
a=b;
b=temp;
}
int main(){
int n,change=0,flag=-1,pos_0,pos_x,t=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(a[i]==0) pos_0=i;
}
while(flag==-1){
if(a[0]!=0){
for(pos_x=0;pos_x<n;pos_x++){
if(a[pos_x]==pos_0) break;
}
swap(a[pos_0],a[pos_x]);
pos_0=pos_x;
change++;
}
else if(a[0]==0){
for(t++;t<n;t++){
if(a[t]!=t){
swap(a[0],a[t]);
pos_0=t;
change++;
break;
}
}
if(t==n) flag=1;// Orderly
}
}
printf("%d",change);
}
notes
- The reason for running timeout is that the time complexity is too high . I fixed the position and moved the element , So every time I look for
if(a[pos_x]==pos_0)
Need to be for loop . You can actually fix elements , Subscript with elements , And the storage location , So every time I lookif(a[pos_x]==pos_0)
No need for loop , And can directly locate !( Thinking is too fixed )
Modified code
#include<stdio.h>
//#include<algorithm>
//using namespace std;
int a[100010];
//int a[100];
void swap(int &a,int &b){
int temp=a;
a=b;
b=temp;
}
int main(){
int n,change=0,flag=-1,t=0,temp;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&temp);
a[temp]=i;
//if(temp==0) pos_0=i;
}
while(flag==-1){
if(a[0]!=0){
swap(a[0],a[a[0]]);
//pos_0=pos_x;
change++;
}
else if(a[0]==0){
for(t++;t<n;t++){
if(a[t]!=t){
swap(a[0],a[t]);
//pos_0=t;
change++;
break;
}
}
if(t==n) flag=1;// Orderly
}
}
printf("%d",change);
}
1038 Recover the Smallest Number
My code
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct Segment{
char it[17];
}segment[10010];
//
bool cmp(Segment a,Segment b){
strcat(a.it,b.it);
strcat(b.it,a.it);
return strcmp(a.it,b.it)<0;
}
int main(){
int n,total=0;
scanf("%d",&n);
while(n--){
char temp[9];
scanf("%s",temp);
int len_temp=strlen(temp),flag=-1;
for(int i=0;i<len_temp;i++){
if(temp[i]!='0'){
flag=1;
break;
}
}
if(flag==1){
strcpy(segment[total++].it,temp);
}
}
if(total==0) printf("0\n");
else{
sort(segment,segment+total,cmp);
int len0=strlen(segment[0].it);
int first_no_zero;
for(first_no_zero=0;first_no_zero<len0;first_no_zero++){
if(segment[0].it[first_no_zero]!='0'){
break;
}
}
for(int i=first_no_zero;i<len0;i++){
printf("%c",segment[0].it[i]);
}
for(int i=1;i<total;i++){
printf("%s",segment[i].it);
}
}
}
notes
- At first I didn't notice if all the inputs were ’000’ character string , Then the output should have a ’0’, This boundary situation .
- However, the last test point still failed after the modification :
- This problem uses a standard template library STL Inside string The type will be better , Maybe the first 6 One test point can pass .
边栏推荐
- Template_ Quick sort_ Double pointer
- [Chongqing Guangdong education] higher mathematics I reference materials of Southwest Petroleum University
- Shell script updates stored procedure to database
- Building the prototype of library functions -- refer to the manual of wildfire
- I changed the driver to 5.1.35, but it is still the same error. I can succeed even now, but I will report this every time I do an SQL operation
- Bigder: I felt good about the 34/100 interview, but I didn't receive the admission
- Patch NTP server at the beginning of DDoS counterattack
- How to improve the enthusiasm of consumers when the member points marketing system is operated?
- Communication between microservices
- [Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 9
猜你喜欢
RobotFramework入门(二)appUI自动化之app启动
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 24
Reset nodejs of the system
纯Qt版中国象棋:实现双人对战、人机对战及网络对战
Network Security Learning - Web vulnerabilities (Part 1)
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 23
Apt installation ZABBIX
Force buckle 146 LRU cache
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 7
Shell script updates stored procedure to database
随机推荐
淘宝焦点图布局实战
深度解析链动2+1模式,颠覆传统卖货思维?
有没有完全自主的国产化数据库技术
Pat grade a 1033 to fill or not to fill
Template_ Quick sort_ Double pointer
数据准备工作
Httprunnermanager installation (III) - configuring myql Database & initialization data under Linux
C语言sizeof和strlen的区别
HttpRunnerManager安装(三)-Linux下配置myql数据库&初始化数据
Maturity of master data management (MDM)
一个复制也能玩出花来
Redis delete policy
Which ecology is better, such as Mi family, graffiti, hilink, zhiting, etc? Analysis of five mainstream smart brands
Accident index statistics
Introduction to robotframework (II) app startup of appui automation
技术分享 | undo 太大了怎么办
After changing the GCC version, make[1] appears in the compilation: cc: command not found
How does yyds dry inventory deal with repeated messages in the consumption process?
The difference between sizeof and strlen in C language
2.11 simulation summary