阿里 4月14笔试 --校招
两道编程题：
已AC一道 另外一道通过百分之30case。
第一题：求出最大密集度，题意大概如下（原文不记得啦）：给定一个n（数组的长度） 给定一个数组，对于这个数组中必存在一个k值，在该数组中有连续的k个数均大于k，求出最大的k值。
例：
输入：
5
3 1 4 5 2
输出：
2
例如：
输入：
5
1 2 3 4 5
输出：
3
这道题只通过了 30% 也不知是那里出现了问题....个人用的是优先队列结合动态规划去做，不断的更新最优值（下面附上代码 恳请大佬指正）
#include<bits/stdc++.h>#include<queue>using namespace std;int main(){int n;cin>>n;int arr[n];for(int i=0; i<n; i++)cin>>arr[i];
int best_ans=1; //最优值最下肯定为一
priority_queue <int ,vector<int> ,greater<int> > prip; //让最小的在队头，因为只需比较最小的和k的关系for(int i=0;i<n;i++){prip.push(arr[i]);int k = prip.size();if(prip.top()>=k) //满足添加进去的规则{best_ans=max(best_ans,k); //更新最优值}else{ //不满足添加进去，把队列清空while(!prip.empty())prip.pop();
prip.push(arr[i]); //从当前位置再次探寻。}}cout<<best_ans;return 0;}
第二题：
求城市群个数，以及城市群包含的城市数。
题意大概如下：城市之间能互达则这两个城市属于同一个城市群，原每个城市之间都有两两互通的铁路（双向可达），但现在损毁了部分铁路，求城市群个数，以及城市群包含的城市数（升序排列）。
输入：
给定城市的个数n 以及m条损毁铁路的信息
如：
5 5
1 2
2 3
2 4
2 5
3 4
输出：
2
1 4
（一个城市群是2 一个是1 3 4 5）
- 题解：已AC。
