【数据结构】第六周

目录

银行排队——队列

公共钥匙盒——队列

等值子串

KMP模式匹配

大整数相乘

最长公共子串

---

银行排队——队列 【问题描述】 我们大多都有在银行排队的经历，唉，那坑爹的排队啊！现在就让我们来算算我们这些客户平均需要等多久吧。 每天刚开始时银行会开m个窗口来为我们total个客户办理业务，当有客户需要办理业务时，先选择可以办理业务的窗口，如果有多个窗口可以办理业务就选择空闲时间最长的窗口，如果有多个窗口空闲的时间一样长，则选择序号小的窗口办理业务。假设我们每个人来到的时间和办理业务所需要的时间（为了简化问题，采用整数表示时间）都知道了。现在请你算算我们平均需要等待多久呢？请用顺序队列或链式队列来完成本题。 【输入形式】 有多组测试数据，每组数据开始有两个正整数m(<20)和total(<200)，后面有total对整数，对应客户先后到来的时间以及办理业务所需的时间。 【输出形式】 平均等待的时间，保留两位小数。 【样例输入】 2 6 1 3 4 1 5 3 9 2 13 4 13 3 3 14 0 3 2 2 2 4 5 4 7 2 11 3 12 3 12 4 12 1 13 3 15 4 19 1 22 3 23 2 2 5 0 6 0 5 0 6 7 1 7 2 【样例输出】 0.00 0.29 1.20 【提示】  题目中选择办理的窗口有三个状态，实际上从序号自小到大查找可以最早办理业务的窗口就已经满足上述三个状态了。若客户的到来时间相同，现实中并不知道该用户需要多久处理完任务，所以遵循先来的先服务原则。 【要求】 请用顺序队列或链式队列来完成，否则不得分。

20.0

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct people{int start;int time;
}people;typedef struct Q{int front,rear;people peo[100];
}Q;typedef struct work{int num;int start;int over;
}work;void ini(Q &q,int total)
{q.front=q.rear=0;for(int i=0;i<total;i++){int x,y;cin>>x>>y;q.peo[i].start=x;q.peo[i].time=y;q.rear++;}}people delet(Q &q)
{q.front++;return q.peo[q.front-1];
}
bool cmp(work a,work b)
{if(a.over!=b.over)return a.over<b.over;elsereturn a.num<b.num;
}
int main()
{int m,total;  //2 6 1 3 4 1 5 3 9 2 13 4 13 3while(cin>>m>>total)  //m=2 total=6{Q q;int sum=0;ini(q,total);work w[m];for(int i=0;i<m;i++)//窗口初始化 0 0 0；1 0 0； 2 0 0 {w[i].num=i;w[i].start=0;w[i].over=0;}for(int i=0;i<total;i++)//开始处理事件 {sort(w,w+m,cmp);people cur=delet(q);//判断cur的开始与窗口    //队首事件的处理，出队表示处理它if(cur.start>=w[0].over) //新事件的开始事件晚于最小窗口的结束时间 {w[0].start=cur.start;w[0].over=cur.start+cur.time;} else{sum+=w[0].over-cur.start;//15-12w[0].start=w[0].over;//15w[0].over=w[0].over+cur.time;//15+3} //更新前或者后排序}float ave=(1.0*sum)/total;//变floatprintf("%.2f\n",ave); }
}

公共钥匙盒——队列 【问题描述】 　　有一个学校的老师共用N个教室，按照规定，所有的钥匙都必须放在公共钥匙盒里，老师不能带钥匙回家。每次老师上课前，都从公共钥匙盒里找到自己上课的教室的钥匙去开门，上完课后，再将钥匙放回到钥匙盒中。 　　钥匙盒一共有N个挂钩，从左到右排成一排，用来挂N个教室的钥匙。一串钥匙没有固定的悬挂位置，但钥匙上有标识，所以老师们不会弄混钥匙。 　　每次取钥匙的时候，老师们都会找到自己所需要的钥匙将其取走，而不会移动其他钥匙。每次还钥匙的时候，还钥匙的老师会找到最左边的空的挂钩，将钥匙挂在这个挂钩上。如果有多位老师还钥匙，则他们按钥匙编号从小到大的顺序还。如果同一时刻既有老师还钥匙又有老师取钥匙，则老师们会先将钥匙全还回去再取出。 　　今天开始的时候钥匙是按编号从小到大的顺序放在钥匙盒里的。有K位老师要上课，给出每位老师所需要的钥匙、开始上课的时间和上课的时长，假设下课时间就是还钥匙时间，请问最终钥匙盒里面钥匙的顺序是怎样的？ 【输入形式】 　　输入的第一行包含两个整数N, K。 　　接下来K行，每行三个整数w, s, c，分别表示一位老师要使用的钥匙编号、开始上课的时间和上课的时长。可能有多位老师使用同一把钥匙，但是老师使用钥匙的时间不会重叠。 　　保证输入数据满足输入格式，你不用检查数据合法性。 【输出形式】 　输出一行，包含N个整数，相邻整数间用一个空格分隔，依次表示每个挂钩上挂的钥匙编号。 【样例输入】 　5 2 　4 3 3 　2 2 7 【样例输出】 　1 4 3 2 5 【样例说明】 　　第一位老师从时刻3开始使用4号教室的钥匙，使用3单位时间，所以在时刻6还钥匙。第二位老师从时刻2开始使用钥匙，使用7单位时间，所以在时刻9还钥匙。 　　每个关键时刻后的钥匙状态如下（X表示空）： 　　时刻2后为1X345； 　　时刻3后为1X3X5； 　　时刻6后为143X5； 　　时刻9后为14325。 【样例输入】 　5 7 　1 1 14 　3 3 12 　1 15 12 　2 7 20 　3 18 12 　4 21 19 　5 30 9 【样例输出】 　1 2 3 5 4 【评分标准】 　　对于30%的评测用例，1 ≤ N, K ≤ 10, 1 ≤ w ≤ N, 1 ≤ s, c ≤ 30； 　　对于60%的评测用例，1 ≤ N, K ≤ 50，1 ≤ w ≤ N，1 ≤ s ≤ 300，1 ≤ c ≤ 50； 　　对于所有评测用例，1 ≤ N, K ≤ 1000，1 ≤ w ≤ N，1 ≤ s ≤ 10000，1 ≤ c ≤ 100

2

#include<bits/stdc++.h>
using namespace std;
typedef struct br{int w;int s;int c;int r;}br;
bool cmp(br a , br b){return a.w < b.w ;}
int main(){int n,k,i,j,z;cin>>n>>k;int a[1010]; for(i=1;i<=n;i++){a[i]=i;}br br[1010];for(i=0;i<k;i++){cin>>br[i].w>>br[i].s>>br[i].c;br[i].r=br[i].s+br[i].c;}sort(br,br+k,cmp); for(j=1;j<=10100;j++){for(i=0;i<k;i++){if(br[i].r==j){for(z=1;z<=n;z++){if(a[z]==0){a[z]=br[i].w;break;}}}}for(i=0;i<k;i++){if(br[i].s==j){for(z=1;z<=n;z++){if(a[z]==br[i].w){a[z]=0;break; }}}}}for(i=1;i<=n;i++)cout<<a[i]<<" ";return 0;
}

等值子串 【问题描述】如果字符串的一个子串（其长度大于1）的各个字符均相同，则称之为等值子串。试设计一算法，求出串S中一个长度最大的等值子串；如果串S 中不存在等值子串，则输出信息no 【输入形式】输入一个字符串，并以！结束 【输出形式】输出第一个出现的最长字符串，如果没有输出no 【样例输入】aabc123abc123cc! 【样例输出】aa 【样例输入】abceebccadddddaaadd! 【样例输出】ddddd

//3. 等值子串
#include<bits/stdc++.h>
using namespace std;
int main(){string str;cin >> str;int sum = 0, cnt = 0;int temp = 0, a = 1;for(int i = 1; i < str.length(); i++){if(str[i] == str[i - 1]) a++;else {if(a > cnt) {cnt = a;sum = temp;}temp = i;a = 1;}}if(cnt > 1)for(int i = sum; i < sum + cnt; i++)cout << str[i];else cout << "no";
}

KMP模式匹配 【问题描述】KMP算法是字符串模式匹配算法中较为高效的算法之一，其在某次子串匹配母串失败时并未回溯母串的指针而是将子串的指针移动到相应的位置。 【输入形式】3组字符串，每组字符串占一行。每行包含由空格分隔的两个字符串，字符串仅由英文小写字母组成且长度不大于100。 【输出形式】每组数据输出1行，输出后一个字符串在前一个字符串中的位置，如果不匹配，则输出0。 【样例输入】 string str thisisalongstring isa nosubstring subt 【样例输出】 1 5 0 【提示】表示字符串的数据结构可以是字符数组或用串类实现。KMP算法调用很简单，但难的是理解算法的思想。掌握算法的思想才能说是掌握算法。

20.00

下载源文件 得分20.00   最后一次提交时间:2023-03-23 16:46:47 共有测试数据:2 平均占用内存:1.307K    平均CPU时间:0.00742S    平均墙钟时间:0.00766S   测试数据 评判结果 测试数据1 完全正确 测试数据2 完全正确 详细

#include<bits/stdc++.h>
using namespace std;
int KMP( string T , string P, int next[] ,int len1 , int len2 )
{int i = 0 , j = 0;while( i < len1 && j < len2 ){if( j == -1){i++;j=0;}else if( P[j] == T[i] ){i++;j++;}else j = next[ j ];}if( j < len2 )return -1;else return i-j;
}
int main()
{int m=0;int next[405] ;string T ;string P ;while( cin >> T >> P ){   int len1 = T.size();int len2 = P.size();next[ 0 ] = -1;int j = 0, k = -1;while( j < len2 -1 ){if( k == -1){next[ j + 1 ] = 0;j++;k=0;}else if( P[ k ] == P[ j ] ){next[ j + 1 ] = k + 1;j++;k++;}else{k = next[ k ];}}m=KMP(  T ,  P, next ,len1 , len2 );if(m != -1)cout << m+1  << endl;elsecout<< "0" <<endl;}}

大整数相乘 【问题描述】输出两个不超过100位的大整数的乘积。 要求用串这一章的“块链串”知识实现两个大整数的相乘。比如每一个结点存储5位，12345678983426801则需要4个结点；先实现大整数乘上一个一位数；再实现两个大数相加。 用这样的链式存储形式便于计算：12--->34567--->89834--->26801 或者：26801--->89834--->34567--->12 【输入形式】 两个大数 【输出形式】 相乘的结果 【样例输入】 1234567891011121314151617181920 2019181716151413121110987654321 【样例输出】 2492816912877266687794240983772975935013386905490061131076320

20.00

#include <bits/stdc++.h>
using namespace std;
int arr[210];
typedef struct Link
{int  Maxsize ;int  num[5];struct  Link*next;}Link;
Link * Init ( Link *p , char s[] )
{Link *head = p;for(int i = 0 ; s[i] != '\0' ; i++){if(i != 0 && i%5 == 0){p -> next = new  Link;p = p -> next;}p -> num [i % 5] = s[i] -'0';p -> Maxsize = i % 5 ;}p -> next = NULL;return head;
}
void multiplication(Link *head1 , Link *head2 )
{Link *p,*q;int N = 0, M = 0 , i , j , Max = 0,m;for( p = head1 ; p != NULL ; p = p -> next )//遍历a{if(p != head1)N+=5;for( i = 0; i <= p -> Maxsize ; i++ ){for( q = head2 ; q != NULL ; q = q -> next ){if( q != head2 )M+=5;for( j = 0 ; j <= q -> Maxsize ; j++){m = M + N + i + j + 1;arr[ m ] += q -> num [ j ] * p -> num[ i ];Max = Max>m? Max :m;}}M=0;}}for( int k = Max ; k > 0 ; k-- )//进位问题{if( arr [ k ] >= 10 ){arr [ k - 1 ] += arr[ k ]/10;arr[ k ] %= 10;}}int k=0;if(arr [ k ] == 0)k++;for(; k <= Max ;  k++)cout<<arr [ k ];cout<<endl;
}
int main()
{char a[100] , b[100];cin >> a >> b ;Link*head1,*head2;head1 = new Link;head2 = new Link;head1 = Init ( head1 , a );head2 = Init ( head2 , b );multiplication( head1 , head2 );
}

最长公共子串 【问题描述】 给定两个字符串，求出它们两个最长的相同子字符串的长度。 最长公共子串(Longest Common Substring)是一个非常经典的面试题目，在实际的程序中也有很高的实用价值。同学们不应该单单只是写出该问题的基本解决代码而已，关键还是享受把算法一步步的优化，让时间和空间复杂度一步步的减少的惊喜。 【输入形式】 两个字符串 【输出形式】 最长的公共子串，若没有则输出“no” 【样例输入】 acbcbcef abcbced 【样例输出】 bcbce 【温馨提示】 问题的关键不在于提交代码并通过测试数据，而是你是否真正掌握了所有求解的算法。

1.00

#include <bits/stdc++.h> 
using namespace std;
int main()
{   int dp;string  a , b ,temp , arr;int  x , y ;cin >> a >> b ;int len1 = a.size();int len2 = b.size();x = len1 - 1;while(y != len2 ){dp = 0 ;temp = "";for(int i = x, j = y;i <len1 && j < len2 ; i++,j++){if( a[ i ] == b[ j ] )dp++,temp +=  a[ i ];else{dp = 0 ; temp = "";}if( temp.size() > arr.size())arr = temp;}if(x) x--;else y++;}if( arr.size()) cout<< arr ;else cout<<"no";return 0;
}