整站优化系统,网页设计公司经营范围,百度助手app免费下载,网站怎么做啊题目描述 题目分析
考虑题目是否满足贪心。每次施展魔法会使一段连续的竹子高度变为一半左右的平方根。根据样例#xff0c;似乎每次让最高的竹子变短就能得到最优解。
假设魔法一次只能对一根竹子使用#xff0c;永远不出现连续相同高度的竹子#xff0c;那么显然无论使用…题目描述 题目分析
考虑题目是否满足贪心。每次施展魔法会使一段连续的竹子高度变为一半左右的平方根。根据样例似乎每次让最高的竹子变短就能得到最优解。
假设魔法一次只能对一根竹子使用永远不出现连续相同高度的竹子那么显然无论使用魔法的顺序如何使用次数永远都是固定的如果会出现连续相同的竹子先对这排竹子中最高的施展魔法不会对其他竹子的变短次数造成影响。而如果率先对相同高度且不是最高的竹子变短则可能会丧失更多竹子变成连续的机会故贪心策略成立。
接下来是如何检测最高竹子和连续相同竹子如何设计算法是难点。首先想到采用map容器给竹子高度排序排序过程的复杂度为不会超时然后使用深度优先搜索检测最大竹子两个方向上所有相同连续的竹子让这些竹子一起变短。经计算最大高度的竹子最多经过6次变短高度就能变成1因此魔法的最多施展次数约为次如果每次都经过一遍搜索会超时。
为了避免重复检测连续的竹子对DFS进行改良每次搜索到连续竹子在搜索过的竹子上分别添加s\t标记标志从第s根到第t根的竹子都是相同高度的从复杂度上将所有相同高度的连续竹子化为一根差不多是某种程度上的离散化免去了重复的搜索。 我的代码
long long型数据的范围是可以用来记录竹子的高度。敲了几行代码后发现只用一个dfs很难处理已经搜索过的竹子因此使用两个dfs分别向左和向右搜索。
在代码过程中由于不熟悉stl容器语法踩了很多坑比如迭代器的失效问题以及multimap.erase(key)会将对应的所有value都删除。
#include iostream
#include algorithm
#include map
#include stack
#include math.husing namespace std;
typedef long long ll;
int n; //总竹子个数
ll lenth[200002]; //所有竹子高度
int sign[200002][3]; //sign[n][0]和sign[n][1]分别储存了连续竹子的起点和终点坐标
//sign[n][2]为连续竹子的的关键坐标储存在map内
int other[200002]; //多余不用搜索的竹子
multimapll, int M; //从低到高竹子对应的坐标
multimapll, int::iterator it; //迭代器用于取出最后一个元素stackint S; //搜索过的竹子
int large; //搜索过的竹子中序号最大的
int small; //搜索过的竹子中序号最小的/*向右深度优先搜索*/
void dfs1(int n, ll l) { //搜索第n根竹子,长度为ln sign[n][1];large max(large, n); //记录搜索终点if (lenth[n 1] l) { //向右搜索S.push(sign[n 1][1]); //起点以外搜索过的竹子入栈S.push(sign[n 1][2]); //替代多余的关键坐标dfs1(n 1, l);}
}
/*向左深度优先搜索*/
void dfs2(int n, ll l) { //搜索第n根竹子,长度为ln sign[n][0];small min(small, n); //记录搜索起点if (lenth[n - 1] l) { //向左搜索S.push(sign[n - 1][0]); //起点以外搜索过的竹子入栈S.push(sign[n - 1][2]); //替代多余的关键坐标dfs2(n - 1, l);}
}
int main() {//初始化参数for (int i 0; i 200002; i){lenth[i] 0;sign[i][0] i;sign[i][1] i;sign[i][2] i;other[i] 0;}//输入总竹子数cin n;//输入竹子高度for (int i 1; i n; i){ll L;cin L;lenth[i] L; //储存在数组pairll, int P(L, i); //储存在map容器M.insert(P);}/*循环取出最高竹子*/int ans 0;int flag 0; //循环停止的标志while (!flag){large 0;small 200002;it M.end();it--;//此时迭代器指向Map最后一个元素ll k (*it).first;ll v (*it).second;//获取键值对M.erase(it);//删除当前容器元素if (k 1) {flag 1;}/*深度优先搜索*/if (!flag other[v] ! 1) {ans;//记录搜索次数即魔法施展次数dfs1(v, k);dfs2(v, k);lenth[v] floor(sqrt(lenth[v] / 2 1));//更新关键竹子高度sign[v][0] small;sign[v][1] large;sign[v][2] v;lenth[sign[v][0]] lenth[v];lenth[sign[v][1]] lenth[v];/*出栈操作*/while (S.size()) {int i S.top();sign[i][0] small;sign[i][1] large;sign[i][2] v;other[i] 1;lenth[i] lenth[v];S.pop();//更新两边竹子的高度并清除多余的非关键坐标}}/*修改map容器存储*/ll nl floor(sqrt(k / 2 1));pairll, int P(nl, v);M.insert(P);//把新的高度存到Map中}cout ans;return 0;
}
