PAT复习自用——做题解和写过代码的搬运工
/*
前言：模拟题是考试最重要的试题形式，考查对STL掌握的熟练程度
*/
---------------------------------------------------------
//1.字符串填充打印问题----建议刷一下乙级题库
/*
问题描述：将一个序列按照要求的规则排成矩阵形式，比较常见，基本思路无非是构造出矩阵再打印还是一边访问一边打印
存入矩阵中的方式常常使用block模式,即通过元素计数值,每出现cnt%block_size==0时，block_id++;
每遍历一个元素push到block[block_id]中，分好行之后，再根据行内元素的要求进行重排列，如合照中，先排最大值在中间
这里通常需要借助临时矩阵，按照要求填入即可
*/
//PAT-1109 合照
/*
本题的坑点在于
1）多余的人排到最后一行 使用 i<row*k 控制block_id++;
2）排序的时候因为拍照者和被拍者是镜像关系，所以当身高相同时，按照字典序排列的方式要反过来
这一点很难分析出来，只有慢慢看测试样例可以想明白
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 10010;
int n,k;
typedef pair<int,string> PIS;
vector<PIS>s, photo[N],res[N];
bool cmp(PIS a,PIS b)
{
if(a.first==b.first)return a.second>b.second;
return a.first<b.first;
}
int main()
{
cin>>n>>k;
int row = n/k;
while(n--)
{
string id;int height;cin>>id>>height;
s.push_back({height,id});
}
sort(s.begin(),s.end(),cmp);
int block_id = 0,i;
for(i = 0;i<s.size();i++)
{
auto t = s[i];
if(i%row==0&&i<row*k)block_id++;
photo[block_id].push_back(t);
}
for(int i = 1;i<=block_id;i++)
{
res[i] = photo[i];
int mid = res[i].size()/2,now = res[i].size()-2;
res[i][mid] = photo[i][photo[i].size()-1];
for(int l = mid-1,r = mid+1;now>=0;)
{
if(l>=0)res[i][l--] = photo[i][now--];
if(r<res[i].size())res[i][r++] = photo[i][now--];
}
}
for(int i =block_id;i>=1;i--)
{
auto t = res[i];
for(int j = 0;j<t.size();j++)
{
cout<<t[j].second;
if(j!=t.size()-1)cout<<" ";
}
cout<<endl;
}
return 0;
}
//PAT-1105 螺旋矩阵
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010,M = 1001;
int seq[N],n,g[M][M];
int get_col(int n)
{
int col = 0,diff = 0x3f3f3f3f;
for(int i = 1;i<=n;i++)
if(n%i==0)
{
int m = n/i;
if(m>=i&&m-i<diff)col = i,diff = m-i;
}
return col;
}
int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};
int main()
{
cin>>n;
for(int i = 0;i<n;i++)cin>>seq[i];
int col = get_col(n),row = n/col;
sort(seq,seq+n,greater<int>());
for(int i = 0,x = 0,y = 0,d = 0;i<n;i++)//以下代码十分简洁，每一次循环只填一个数
{
g[x][y] = seq[i];
int a = x+dx[d],b = y+dy[d];//这一步比较关键，意思是尝试一下看有没有越界
if(a<0||b<0||a>=row||b>=col||g[a][b])//如果越界，则换个方向
{
d = (d+1)%4;//加%运算，代码十分简洁
a = x+dx[d],b = y+dy[d];
}
x = a,y = b;
}
for(int i = 0;i<row;i++)
{
for(int j = 0;j<col;j++)
cout<<g[i][j]<<" ";
cout<<endl;
}
return 0;
}
//上题是一个经典的蛇形矩阵问题，下面放模板题
/*
https://www.acwing.com/problem/content/758/
输入两个整数n和m，输出一个n行m列的矩阵，将数字 1 到 n*m 按照回字蛇形填充至矩阵中。
具体矩阵形式可参考样例。
*/
#include<iostream>
#include<vector>
using namespace std;
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int main()
{
int n, m; cin >> n >> m;
vector<vector<int>> g(n, vector<int>(m));//初始化vector大小的简洁方式
for (int i = 1, x = 0, y = 0, d = 0; i <= n*m; i++)
{
g[x][y] = i;
int a = x + dx[d], b = y + dy[d];
if (a < 0 || b < 0 || a >= n || b >= m || g[a][b])//这里容易写错为g[x][y],注意
{
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
x = a, y = b;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
cout << g[i][j] << " ";
cout << endl;
}
}
// PAT-1031 U 形 Hello World
/*
思路：双指针（i,j）从两边开始一边打印一边输出，特判最后一行
比较麻烦就在于这个行数不等式的求解
*/
#include<iostream>
using namespace std;
int get_row(int n)
{
int row = 0;
for(int n2 = n;n2>=3;n2--)
if((n+2-n2)%2==0&&(n+2-n2)/2<=n2)row = (n+2-n2)/2;
return row;
}
int main()
{
string str;cin>>str;
int n1 = get_row(str.size()),n2 = str.size()+2-2*n1;
int i,j,cnt = 0;
for(i = 0,j = str.size()-1;i<j;i++,j--,cnt++)
{
if(cnt<n1-1)cout<<str[i]<<string(n2-2,' ')<<str[j]<<endl; //特判最后一行不只输出两个字符
//string 输出或补充空格的简便方法string(num,' ')
else break;
}
while(i<=j)cout<<str[i++];
return 0;
}
/*
分形，具有以非整数维形式充填空间的形态特征。
通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状”，
即具有自相似的性质。
现在，定义“盒子分形”如下：
一级盒子分形：
X
二级盒子分形：
X X
X
X X
如果用B(n - 1)代表第n-1级盒子分形，那么第n级盒子分形即为：
B(n - 1) B(n - 1)
B(n - 1)
B(n - 1) B(n - 1)
你的任务是绘制一个n级的盒子分形。
考查知识点：分形，递归，坐标变换
观察规律:每一次输出都是一个正方形，边长都是3^(n-1)，本题可以优化到只有一个递归分支，成为链式递归问题
每次递归的过程在于把上一次递归的结果复制4遍,如上图的B(n-1) 分布
可以开一个数组sx[] = {0,1,2,2},sy[] = {2,1,0,2},表示每次复制的起始坐标(x,y)
*/
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 1000,M = 300000;
int g[N][N],d[N];
void dfs(int n)
{
if(n==1)
{
g[0][0] = 1;
return;
}
dfs(n-1);
int len = pow(3,n-2);
int sx[] = {0,1,2,2},sy[] = {2,1,0,2};
for(int k = 0;k<4;k++)
for(int i = 0;i<len;i++)
for(int j = 0;j<len;j++)
g[sx[k]*len+i][sy[k]*len+j] = g[i][j];
}
int main()
{
memset(g,0,sizeof g);
int x;
while(cin>>x)
{
if(x==-1)break;
dfs(x);
for(int i = 0;i<pow(3,x-1);i++)
{
int maxcol = 0;
for(int j = 0;j<pow(3,x-1);j++)
if(g[i][j])maxcol = j;
d[i] = maxcol;
}
for(int i = 0;i<pow(3,x-1);i++)
{
for(int j = 0;j<=d[i];j++)
if(g[i][j])cout<<"X";
else cout<<" ";
cout<<endl;
}
puts("-");
}
return 0;
}
--------------------------
/*
2.字符串判定问题
考虑问题是否全面
1)合法性问题
2)
*/
https://www.acwing.com/solution/content/737/
//字符串循环移位的判定
bool check(string a,string b)
{
if(a.size()<b.size())swap(a,b);
a+=a;
if(a.find(b)!=string::npos)return true;
else return false;
}
------------------------
/*
2.枚举问题
模拟题的枚举问题十分常见，通常题目给出若干询问，让我们一一对所给序列做一些枚举判断性质是否满足
如图论判断是否为简单环路，只需要顺次枚举是否连边，并统计每个点是否只出现一次，再检查是否是首尾相接的
这里枚举最重要的思想就在于如何定义枚举顺序，如何将高维的枚举问题通过排序，等效的方式转化为低维问题
一般而言最多两层循环，故一般考试都是两层枚举，给出的点数在1000左右，否则要思考别的解法
图论的模拟练习请移步图论专题
*/
//PAT-1128 N_queen_puzzle 在了解了N皇后如何实现之后，本问题十分容易解决，把check的部分确定好即可
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,seq[N];
int main()
{
cin>>n;
while(n--)
{
int cnt;cin>>cnt;
bool flag = true;
set<int> s;
for(int i = 1;i<=cnt;i++)
{
cin>>seq[i];
if(s.count(seq[i]))flag = false;
s.insert(seq[i]);
for(int pre = 1;pre<i;pre++)
if(abs(pre-i)==abs(seq[pre]-seq[i]))flag = false;
}
if(flag)puts("YES");
else puts("NO");
}
return 0;
}
------------------------------------
/*
3.哈希问题
*/
//PAT-1129 推荐系统
/*
使用一个哈希表记录物品的访问次数，同时动态维护一个k-最佳队列
动态维护队列的思想在于队列的长度有限，且考虑到时间复杂度问题将队列长度设计的较短
因此维护（排序，插入，删除）队列的成本较低
*/
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
int n,k;
const int N = 100100;
int cnt[N];
unordered_map<int,bool> st;
vector<int> top_k;
bool cmp(int x,int y)
{
if(cnt[x]==cnt[y])return x<y;
else return cnt[x]>cnt[y];
}
int main()
{
scanf("%d %d",&n,&k);
for(int i = 0;i<n;i++)
{
int x;scanf("%d",&x);
if(i)
{
printf("%d:",x);
for(int j = 0;j<top_k.size()&&j<k;j++)
printf(" %d",top_k[j]);
puts("");
}
cnt[x]++;
//update top_k，只需要动态维护队尾元素的插入即可，因为最后一步要排序
if(st[x]==false)
{
if(top_k.size()==k&&
(cnt[top_k[k-1]]<cnt[x]||
(cnt[top_k[k-1]]==cnt[x]&&x<top_k[k-1])
)
)
st[top_k[k-1]] = false,top_k[k-1] = x,st[x] = true;//替换的两个元素交换标记，然后替换即可
else if(top_k.size()==k);
else top_k.push_back(x),st[x] = true;
}
sort(top_k.begin(),top_k.end(),cmp);
}
return 0;
}
/*
4.STL考查问题
这里列举了一些考查stl操作比较明显的问题，或者一些操作不太熟练的stl问题
如队列的模拟，栈的模拟，图的模拟（判断回路，验证性质，检验顺序）
*/
-------------------------------------------------------
//（一）队列模拟
/*
十分常考的问题，因为队列的应用不仅在计算机中十分广泛，而且许多实际问题可以抽象为队列或排队问题
PAT考过2次排队问题，需要重点掌握
*/
//单调栈的合法弹出序列——模拟栈操作，抓住这里的单调，分情况讨论，需要好好利用这个测试样例理解题意
#include<iostream>
#include<vector>
using namespace std;
const int N = 1001;
int seq[N],n,m,k;
vector<int> mystack;
bool check()
{
int t = seq[0];
for(int i = 1;i<=t;i++)mystack.push_back(i);
if(mystack.size()>m)return false;
mystack.pop_back();
for(int i = 1;i<n;i++)
{
int u = seq[i];
if(u>t)
{
for(int j = t+1;j<=u;j++)mystack.push_back(j);
if(mystack.size()>m)return false;
mystack.pop_back();
t = u;
}
else
{
int v = mystack.back();
if(v==u)mystack.pop_back();
else return false;
}
}
return true;
}
int main()
{
cin>>m>>n>>k;
while(k--)
{
mystack.clear();
for(int i = 0;i<n;i++)cin>>seq[i];
if(check())puts("YES");
else puts("NO");
}
return 0;
}
//L2-014列车调度
/*
必须要车号大的先出，小的后出。所以列车排队的每一队必须是从大到小排列（从右往左看），
才能保证开出去的车也是从大到小的。对于每一个想要进入并列铁轨的车，如果车号大于每一队的队尾的车号，
说明不能进入已经有的队伍，必须进入新的铁轨，否则，选择一个最接近它车号的尾部车号的队伍进入。
其实无需保存每一个并行队列的所有值，只需要保存当前队伍的车尾（就是每一列最左边 即 每一列的最小值）即可，
因为每一次都是需要排序比较大小的，所以用set自动排序，首先把set里面放入一个0值。
每一次set的最后一个值s.rbegin()都是当前所有队列队尾的最大值。如果当前想要进入排队队伍的t值比集合里面最大值小，
就移除第一个比他大的值，然后把t插入集合中。表示的是将t值插入了最接近它车号的队伍的队尾，否则就直接插入进去t值。
作为新的队伍。s.upper_bound(t)返回的是第一个大于t的迭代器的位置，在前面加星号表示取这个位置的值，
所以s.erase(*(s.upper_bound(t)));
表示删除当前这个刚好大于t的位置处的值。因为一开始插入了一个没有的0，所以最后输出是s.size()-1;
*/
//使用双重循环会超时
#include<iostream>
#include<vector>
using namespace std;
const int N = 1010;
vector<int> trail[N];
int n,seq[N];
int main()
{
cin >> n;
int idx = 0;
for (int i = 0; i < n; i++)
{
cin >> seq[i];
bool flag = false;
if (i == 0)trail[0].push_back(seq[i]);
else
{
for (int j = 0; j <= idx; j++)
{
int t = trail[j].back();
if (seq[i] < t)
{
trail[j].push_back(seq[i]);
flag = true;
break;
}
}
if (!flag)trail[++idx].push_back(seq[i]);
}
}
cout << idx+1 << endl;
return 0;
}
//柳神代码——使用STL中的set保持自然有序，保存每条轨道的末尾值
#include <iostream>
#include <set>
using namespace std;
int main() {
int n, t;
cin >> n;
set<int> s;
s.insert(0);
for(int i = 0; i < n; i++) {
cin >> t;
if(t < *s.rbegin()) {
s.erase(*(s.upper_bound(t)));
}
s.insert(t);
}
cout << s.size() - 1;
return 0;
}
//队列实际应用模拟
/*
类型1：单队列多窗口一般问题：
假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。
本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。
思路：依次取出队头，选择窗口，这里一定要分两种情况
如果到达的时候没有窗口空闲，则需要等待，此时选择的是结束时间最早的窗口
而若不需要等待，则选择序号最小的空闲窗口
*/
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 1001,M = 10;
int n,k,q[M],cnt[M];
struct Person
{
int arrive,service;
}person[N];
int main()
{
cin>>n;
queue<Person>qt;
for(int i = 0;i<n;i++)
{
int a,b;cin>>a>>b;
b = min(b,60);
qt.push({a,b});
}
cin>>k;
double wait = 0;
int maxwait = 0,lastend = 0;
while(!qt.empty())
{
auto t = qt.front();
qt.pop();
int a = t.arrive,s = t.service,service_time;
int wid = -1,minend = 0x3f3f3f3f;
for(int j = 0;j<k;j++)
if(q[j]<=a)
{
wid = j;
break;
}
if(wid==-1)
{
for(int j = 0;j<k;j++)
{
if(minend>q[j])
{
wid = j;
minend = q[j];
}
}
service_time = minend;
}
else service_time = a;
int wt = service_time-a;
wait+=wt,q[wid] = service_time+s,cnt[wid]++,
lastend = max(q[wid],lastend),
maxwait = max(wt,maxwait);
}
printf("%.1lf %d %d\n",wait/n,maxwait,lastend);
for(int i = 0;i<k;i++)
{
cout<<cnt[i];
if(i!=k-1)cout<<" ";
}
return 0;
}
/*
类型2：单队列多窗口+VIP队列
假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。
当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。
有些银行会给VIP客户以各种优惠服务，例如专门开辟VIP窗口。为了最大限度地利用资源，VIP窗口的服务机制定义为：
当队列中没有VIP客户时，该窗口为普通顾客服务；当该窗口空闲并且队列中有VIP客户在等待时，
排在最前面的VIP客户享受该窗口的服务。同时，当轮到某VIP客户出列时，若VIP窗口非空，该客户可以选择空闲的普通窗口；
否则一定选择VIP窗口。本题要求输出前来等待服务的N位顾客的
平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。
分析题意可以发现限制如下：
1）检查队列中没有vip时，同单队列多窗口问题
2）检查队列中有vip时，服务最前方的vip用户，且该用户优先选择vip窗口
解题思路：
1、普通客户到来：从编号最小的窗口开始查看是否有空闲窗口
1）如果有空闲窗口，若此时空闲窗口刚好是VIP窗口，则看一下队列里面是否有已经到来的VIP客户，如有，则让该VIP插队
2）如果没有空闲窗口，则寻找最先完成的窗口，若最先完成的窗口也是VIP，同理也要看一下队列里是否有VIP已经到来，
如有，则让VIP插队
2、VIP客户到来：首先查看VIP窗口是否空闲，如空闲，则直接办理，若不空闲，
则寻找最快完成窗口（这里要注意的是：VIP窗口的优先级排在普通窗口之前）
*/
#include<iostream>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1001, M = 10,INF = 0x3f3f3f3f;
struct Person
{
int id,arrive_time, service_time, start_time;
bool operator>(const Person p)const
{
if (arrive_time == p.arrive_time)return id > p.id;
return arrive_time > p.arrive_time;
}
};
struct window
{
int id,end_time;
bool operator>(const window w)const
{
if (end_time == w.end_time)return id > w.id;
return end_time > w.end_time;
}
};
priority_queue<Person, vector<Person>, greater<Person>> vip_person,normal_person;
priority_queue<window, vector<window>, greater<window>> vip_window,normal_window;
int n,m,k,cnt[M],maxwait = 0,maxfinish = 0;
double wait = 0;
void assign(priority_queue<Person, vector<Person>, greater<Person>>&per,
priority_queue<window, vector<window>, greater<window>> &win)
{
auto w = win.top(); win.pop();
auto p = per.top(); per.pop();
cnt[w.id]++;
wait += (w.end_time - p.arrive_time);
maxwait = max(w.end_time - p.arrive_time, maxwait);
p.start_time = w.end_time;
w.end_time = p.start_time + p.service_time;
win.push(w);
maxfinish = max(p.start_time+p.service_time, maxfinish);
}
int main()
{
cin >> n;
vip_person.push({ -1,INF });normal_person.push({ -1,INF });
for (int u = 0; u < n; u++)
{
int a, b, c;
cin >> a >> b >> c;
b = min(60, b);
if (c)vip_person.push({ u,a,b });
else normal_person.push({ u,a,b });
}
cin >> m >> k;
vip_window.push({ -1,INF });
normal_window.push({ -1,INF });
for (int i = 0; i < m; i++)
if (i == k)vip_window.push({ i,0 });
else normal_window.push({ i,0 });
while (normal_person.size() > 1 || vip_person.size() > 1)
{
auto vp = vip_person.top();
auto np = normal_person.top();
int arrive_time = min(vp.arrive_time, np.arrive_time);
while (normal_window.top().end_time < arrive_time)
{
auto t = normal_window.top();
normal_window.pop();
t.end_time = arrive_time;
normal_window.push(t);
}
while (vip_window.top().end_time < arrive_time)
{
auto t = vip_window.top();
vip_window.pop();
t.end_time = arrive_time;
vip_window.push(t);
}
auto nw = normal_window.top();
auto vw = vip_window.top();
int end_time = min(nw.end_time, vw.end_time);
if (end_time == vw.end_time && vp.arrive_time <= end_time)assign(vip_person, vip_window);
else if (np>vp)
{
if (vw.end_time <= vp.arrive_time)assign(vip_person, vip_window);
else assign(vip_person, normal_window);
}
else
{
if (nw > vw)assign(normal_person, vip_window);
else assign(normal_person, normal_window);
}
}
printf("%.1lf %d %d\n", wait / n, maxwait, maxfinish);
for (int i = 0; i < m; i++)
{
cout << cnt[i];
if (i != m-1)cout << " ";
}
return 0;
}
//VIP队列练习——乒乓球
#include<iostream>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int n, m, k;
const int M = 110, N = 10010,INF = 0x3f3f3f3f;
struct Person
{
int arrive_time, play_time;
int wait_time, start_time;
bool operator<(const Person p)const //sort
{
if (start_time == p.start_time)return arrive_time < p.arrive_time;
return start_time < p.start_time;
}
bool operator>(const Person p)const
{
return arrive_time > p.arrive_time;
}
};
struct Table
{
int id,end_time;
bool operator >(const Table t)const
{
if (end_time == t.end_time)return id > t.id;
return end_time > t.end_time;
}
};
int cnt[M];
vector<Person> persons;
void assign(priority_queue<Person, vector<Person>, greater<Person>> &per,
priority_queue<Table, vector<Table>, greater<Table>> &tab)
{
auto t = tab.top(); tab.pop();
auto p = per.top(); per.pop();
cnt[t.id]++;
p.wait_time = round((t.end_time - p.arrive_time)/60.0);
p.start_time = t.end_time;
persons.push_back(p);
t.end_time = p.start_time + p.play_time;
tab.push(t);
}
bool is_vip_table[M];
priority_queue<Person, vector<Person>, greater<Person>> vip_person, normal_person;
priority_queue<Table, vector<Table>, greater<Table>> vip_table, normal_table;
int main()
{
cin >> n;
normal_person.push({ INF }), vip_person.push({ INF });
normal_table.push({ -1,INF }), vip_table.push({ -1,INF });
for (int i = 0; i < n; i++)
{
int hour, minute, second,play_time,is_vip;
scanf("%d:%d:%d %d %d", &hour, &minute, &second, &play_time, &is_vip);
int seconds = hour * 3600 + minute * 60 + second;
play_time = min(120, play_time);
play_time *= 60;
if (is_vip)vip_person.push({ seconds,play_time });
else normal_person.push({ seconds,play_time });
}
cin >> m >> k;
for (int i = 0; i < k; i++)
{
int x; cin >> x; is_vip_table[x] = true;
}
for (int i = 1; i <= m; i++)
{
if (is_vip_table[i])vip_table.push({ i,8 * 3600 });
else normal_table.push({ i,8 * 3600 });
}
while (normal_person.size() > 1 || vip_person.size() > 1)
{
auto pn = normal_person.top();
auto pv = vip_person.top();
int arrive_time = min(pn.arrive_time, pv.arrive_time);
while (normal_table.top().end_time < arrive_time)
{
auto t = normal_table.top();
normal_table.pop();
t.end_time = arrive_time;
normal_table.push(t);
}
while (vip_table.top().end_time < arrive_time)
{
auto t = vip_table.top();
vip_table.pop();
t.end_time = arrive_time;
vip_table.push(t);
}
auto vt = vip_table.top();
auto nt = normal_table.top();
int end_time = min(vt.end_time, nt.end_time);
if (end_time >= 21 * 3600)break;
if (end_time == vt.end_time && pv.arrive_time <= end_time)
assign(vip_person, vip_table);
else if (pn.arrive_time < pv.arrive_time)
{
if (vt > nt)assign(normal_person, normal_table);
else assign(normal_person, vip_table);
}
else
{
if (vt > nt)assign(vip_person, normal_table);
else assign(vip_person, vip_table);
}
}
for (int i = 0; i < persons.size(); i++)
{
int t = persons[i].arrive_time;
int hour = t / 3600, minute = (t % 3600) / 60, sec = t % 60;
printf("%02d:%02d:%02d ", hour, minute, sec);
t = persons[i].start_time;
hour = t / 3600, minute = (t % 3600) / 60, sec = t % 60;
printf("%02d:%02d:%02d %d\n", hour, minute, sec,persons[i].wait_time);
}
for (int i = 1; i <= m; i++)
{
cout << cnt[i];
if (i != m)cout << " ";
}
return 0;
}
/*
单队列单窗口带夹塞板
排队“夹塞”是引起大家强烈不满的行为，但是这种现象时常存在。在银行的单窗口排队问题中，
假设银行只有1个窗口提供服务，所有顾客按到达时间排成一条长龙。当窗口空闲时，
下一位顾客即去该窗口处理事务。此时如果已知第i位顾客与排在后面的第j位顾客是好朋友，
并且愿意替朋友办理事务的话，那么第i位顾客的事务处理时间就是自己的事务加朋友的事务所耗时间的总和。
在这种情况下，顾客的等待时间就可能被影响。假设所有人到达银行时，若没有空窗口，
都会请求排在最前面的朋友帮忙（包括正在窗口接受服务的朋友）；当有不止一位朋友请求某位顾客帮忙时，
该顾客会根据自己朋友请求的顺序来依次处理事务。试编写程序模拟这种现象，并计算顾客的平均等待时间。
思路：
每次出队的时候检查
是否已经服务过，若没服务过，
则设置访问标记，
更新等待时间，然后把当前时间增加到他完成服务并离开的时间
检查是否属于某个朋友圈，若属于朋友圈，则遍历朋友圈vector（需要事先按照到达时间排序）
依次增加时间
设置访问标记
*/
#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N = 10010,M = 110;
int n, m,idx = 0;
typedef pair<int, string> PIS;
unordered_map<string, int> s2i,p;
struct Person
{
string name;
int arr, ser;
}person[N];
vector<PIS> heap[M];
unordered_map<string, bool> st;
queue<int> q;
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int cnt; cin >> cnt;
while (cnt--)
{
string id; cin >> id;
p[id] = i;
}
}
for (int i = 0; i < n; i++)
{
string id; int a, b; cin >> id >> a >> b;
b = min(60, b);
s2i[id] = idx;
person[idx] = { id,a,b };
if (p.count(id))
heap[p[id]].push_back({ a,id });
q.push(idx);
idx++;
}
int now = 0,cnt = 0;
double wait = 0;
for (int i = 1; i <= m; i++)
sort(heap[i].begin(), heap[i].end());
vector<string> res;
while (!q.empty())
{
int t = q.front();
q.pop();
string name = person[t].name;
if (st[name])continue;
res.push_back(name);
st[name] = true;
int tp = p[name],s = person[t].ser,a = person[t].arr;
now = max(now, a);
wait += now - a;
now += s;
if (tp != 0)
{
for(int k = 0;k<heap[tp].size();k++)
{
auto pt = heap[tp][k];
if (st[pt.second])continue;
int arrive = person[s2i[pt.second]].arr;
int service = person[s2i[pt.second]].ser;
if (arrive > now)
break;
else
{
wait += (now - arrive);
now += service;
st[pt.second] = true;
res.push_back(pt.second);
}
}
}
}
for (int i = 0; i < res.size(); i++)
cout << res[i] << endl;
printf("%.1lf\n", wait / n);
return 0;
}
/*
用两个栈实现队列操作
具体思路比较难想，合理的解法是，输入时，先入栈到容量较小的栈(a)，此时的出队依次将元素弹入另一个栈，并输出最后元素
然后再压回来，若该栈满了，则依次弹出栈中所有元素并压入容量较大的栈，该情况的出队情况是直接弹出容量较大的栈顶元素
*/
#include<iostream>
#include<stack>
using namespace std;
stack<int>a,b;
int n1,n2;
int main()
{
cin>>n1>>n2;
if(n1>n2)swap(n1,n2);//保证n1<n2
while(true)
{
string cmd;int item;
cin>>cmd;
if(cmd=="T")break;
if(cmd=="A")
{
cin>>item;
if(a.size()==n1&&b.size()==0)
while(a.size())b.push(a.top()),a.pop();
if(a.size()==n1&&b.size())
puts("ERROR:Full");
else a.push(item);
}
else if(cmd=="D")
{
if(a.size()==0&&b.size()==0)puts("ERROR:Empty");
else
{
if(b.size()==0)
while(a.size())b.push(a.top()),a.pop();
cout<<b.top()<<endl;
b.pop();
}
}
}
return 0;
}
//windows消息队列模拟，考查优先队列priority_queue的使用
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,string> msg;
int n;
int main()
{
cin>>n;
priority_queue<msg,vector<msg>,greater<msg>> q;
for(int i = 0;i<n;i++)
{
string cmd,message;int priority;
cin>>cmd;
if(cmd=="PUT")
{
cin>>message>>priority;
q.push({priority,message});
}
else
{
if(!q.size())puts("EMPTY QUEUE!");
else
{
auto t = q.top();
q.pop();
cout<<t.second<<endl;
}
}
}
return 0;
}
/*
判断合法的dfs序列---模拟dfs，即受限dfs，根据访问序列进行dfs
使用一个vector模拟一个队列
考查vector中的find和删除元素的操作
*/
#include<iostream>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1001;
int n,m,g[N][N],seq[N],degree[N],tmp[N];
bool st[N];
vector<int>p[N];
bool check()
{
bool flag = true;
vector<int>s;s.push_back(seq[0]);//初始化栈
for(auto c:p[seq[0]])tmp[c]--;
for(int i = 1;i<n;i++)//使用vector模拟栈
{
if(s.size()==0){flag = false;break;}//没有可达的点
int v = seq[i],u = s.back();
if(g[u][v])
{
for(auto c:p[v])
{
tmp[c]--;
if(tmp[c]==0)
{
auto it = find(s.begin(),s.end(),c);//所有入边对应的顶点出度减一
if(it!=s.end())s.erase(it);
}
}
if(tmp[v])s.push_back(v);
if(tmp[v]==0&&i==n-2)break;//到达最后一个节点
}
else flag = false;//当前顶点和栈顶不相连
}
return flag;
}
int main()
{
cin>>n>>m;
while(m--)
{
int x,y;cin>>x>>y;
g[x][y] = 1;
p[y].push_back(x);
degree[x]++;
}
int cnt;
cin>>cnt;
while(cnt--)
{
for(int i = 0;i<n;i++){cin>>seq[i];tmp[i] = degree[i];}
if(check())puts("Yes");
else puts("No");
}
return 0;
}
/*
字符串stl考查
词频统计
请编写程序，对一段英文文本，统计其中所有不同单词的个数，以及词频最大的前10%的单词。
所谓“单词”，是指由不超过80个单词字符组成的连续字符串，但长度超过15的单词将只截取保留前15个单词字符。
而合法的“单词字符”为大小写字母、数字和下划线，其它字符均认为是单词分隔符。
输入格式:
输入给出一段非空文本，最后以符号#结尾。输入保证存在至少10个不同的单词。
输出格式:
在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写，例如“PAT”和“pat”被认为是同一个单词。
随后按照词频递减的顺序，按照词频:单词的格式输出词频最大的前10%的单词。若有并列，则按递增字典序输出。
*/
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
map<string,int> mp;
struct P
{
string word;int num;
bool operator<(const P x)
{
if(num==x.num)return word<x.word;
else return num>x.num;
}
};
int main()
{
string str;
while(getline(cin,str))
{
int i = 0;
while(i<str.size())
{
string word;
while(str[i]<='z'&&str[i]>='a'||
str[i]<='Z'&&str[i]>='A'||str[i]=='_'||
str[i]<='9'&&str[i]>='0')
word+=tolower(str[i++]);//检查合法单词组成
if(word.size()>80)continue;//超过80不算
if(word.size()>15)word = word.substr(0,15);//小于80但超过15算前15
mp[word]++;
i++;
}
if(str[str.size()-1]=='#')break;
}
auto p = mp.find("");//去掉空字符
mp.erase(p);
cout<<mp.size()<<endl;
vector<P>res;
for(auto c:mp)res.push_back({c.first,c.second});
int cnt = (int)(res.size()*0.1);
sort(res.begin(),res.end());
for(int i = 0;i<cnt;i++)
cout<<res[i].num<<":"<<res[i].word<<endl;
return 0;
}
/*
5.另类模拟问题
问题描述较为复杂，思维较为跳跃，或具有一定逻辑背景的问题，如海盗分赃就涉及到简单的博弈论知识
*/
//海盗分赃
/*
相关阅读：
https://blog.csdn.net/TOBEALISTENNER/article/details/79896856?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
https://www.cnblogs.com/snzhong/p/12588915.html
该题的本质是递归地进行预测，需要有一定的博弈论基础理解，手动模拟出表之后可以发现一些规律求解
1 2 3 4 5 6 7 拉拢人数
10 0
0 10 1
9 1 0 1
7 0 2 1 2
7 0 1 0 2 2
6 0 1 2 1 0 3
6 0 1 2 0 0 1 3
然后我们来看固定金币数之后，人数对结果的影响
1 D
2 0 D
3 D-1 1 0
4 D-3 0 2 1
5 D-3 0 1 0 2
6 D-4 0 1 2 1 0
......
我们发现，当人数大于3的时候只需要给上次分配到0金币的人1个金币，分配到1金币的人2金币即可
*/
//递推版本---需要再琢磨琢磨
#include <stdio.h>
#include <string.h>
#define Max 100+1
int main() {
int d,p;
scanf("%d %d",&d,&p);
int ans[p+1];
memset(ans,0,sizeof(ans));
int pos=p-2;//倒数第3个海盗开始
while(pos!=0) {//从后向前枚举（n-2--->0）
ans[pos]=d;
int cnt=(p-pos+1)/2;//拉拢人数
int max=0;
int i;
int flag[p+1];
memset(flag,0,sizeof(flag));//每一遍扫描要判断是否拉拢，拉拢过的人就过滤
while(cnt!=0) {
for(i=pos+1; i<=p; i++) {//寻找下一轮分配到最少钻石的海盗，进行拉拢
if(ans[i]==max&&!flag[i]) {
ans[i]++;
flag[i]=1;
cnt--;
}
if(!cnt)
break;
}
max++;//枚举上一次分配到0金币的，1金币的...
}
for(i=pos+1; i<=p; i++) {
if(flag[i]) {
ans[pos]-=ans[i];
} else
ans[i]=0;
}
pos--;
}
printf("%d",ans[1]);
return 0;
}
//高效规律版本
#include<iostream>
using namespace std;
int main()
{
int d,p;
cin>>d>>p;
if(p==3)cout<<d-1<<endl;
else cout<<d-(p/2+1)<<endl;
return 0;
}
zan%%%
感谢分享