做集团网站的,手机网站生成小程序,修改wordpress设置方法,大宗商品价格查询网站文章目录 写在前面14666-优先屏障思路编程 14847-Masha与老鼠思路编程 写在前面
昨天刷的这两道题写了很久#xff0c;特别是Masha与老鼠这道题#xff0c;写了都快3个小时#xff0c;主要还是理解代码逻辑有点难#xff0c;不过写完之后感觉收获挺大的#xff0c;给我以… 文章目录 写在前面14666-优先屏障思路编程 14847-Masha与老鼠思路编程 写在前面
昨天刷的这两道题写了很久·····特别是Masha与老鼠这道题写了都快3个小时主要还是理解代码逻辑有点难不过写完之后感觉收获挺大的给我以后刷题提供很好的思路
14666-优先屏障
思路
考点单调栈前缀后缀模拟 我们先不考虑屏障的位置先考虑某个点往前面看和往后面看监视的总个数很容易想到前缀和后缀的思路在此之前先说栈的用处栈用来存放每次遍历过的山的高度先说前缀的思路从头遍历每次先加上前面监视的个数判断当前栈顶元素是否小于当前元素如果小于将栈顶排除计数器1如果当前元素的高度大于栈顶元素那么之后的山都看不到栈顶元素的山所以直接将他排出去如果栈为空加上计数器反之加上计数器的同时在1当前的山和栈顶的山可以相互监视然后再将当前元素进栈后缀同理然后再从头遍历由于加完屏障左边的只能看前面右边的只能看后面所以考虑前缀[i-1]和后缀[i]相加最小值即可
编程
const int N5e45;
int a[N],qz[N],hz[N];
int num1;
void solve(){memset(hz,0,sizeof hz);stackint st; int n;cin n;for(int i1;in;i) cin a[i];for(int i1;in;i){int sum0;qz[i]qz[i-1];while(!st.empty() st.top()a[i]){//判断是否需要排除栈顶元素sum;st.pop(); }if(st.empty()) qz[i]sum;//栈为空加上计数器else qz[i]sum1;//不为空加上计数器在加上本身st.push(a[i]);}while(!st.empty()) st.pop();for(int in;i1;--i){int sum0;hz[i]hz[i1];while(!st.empty() st.top()a[i]){sum;st.pop(); }if(st.empty()) hz[i]sum;else hz[i]sum1;st.push(a[i]);}int maxn0,k0;int mxqz[n];//总的监视个数for(int i1;in;i){if(mx-(qz[i-1]hz[i])maxn){//前缀和后缀相加的值最小maxnmx-(qz[i-1]hz[i]);ki;}}cout Case # num : k maxn endl;return ;
}14847-Masha与老鼠
思路
考点贪心反悔贪心 根据贪心策略每只老鼠有两个选择左边最近的有容量的洞右边最近的有容量的洞
优先队列q1存老鼠q2存洞按坐标大小出队。老鼠存的值为-k-x洞存的值为-xx为该点坐标k为偏差值。
输入一个洞-鼠-洞-鼠-洞样例仔细观察。当鼠2进洞2时鼠1的位置被挤掉那么鼠1就会回到上一个状态k值算的就是所有现状态回到上一个状态时的偏差值的累加即ans k就能让ans回到上一个状态。 讲起来比较抽象具体看代码
编程
const int N2e650;
PII p[N];
priority_queueint,vectorint,greaterint q1;//存老鼠
priority_queuePII,vectorPII,greaterPII q2;//存洞用pair存洞的位置和下标
void solve(){int n,m;cin n m;int sumn;int ans0;for(int i1;in;i) cin p[i].fi;for(int i1;im;i){cin p[in].fi p[in].se;sum-p[in].se;}nm;if(sum0){//无解只要判断洞的总数小于老鼠总数即可cout -1 endl;return ;}sort(p1,p1n);//将老鼠和洞的位置按升序排序for(int i1;in;i){int xp[i].fi;if(p[i].se){//洞while(p[i].se !q1.empty() xq1.top()0){//将q1.top展开x1-x2k,意思为当前坐标减去老鼠坐标小于之前他们的差值int kxq1.top();ansk;//加上差值q1.pop();--p[i].se;q2.push({-k-x,0});//提供反悔次数如果后边的老鼠进入当前这个洞则会将当前老鼠挤回前面那个洞这里-k为这个老鼠进入这个洞和进入前面那个洞之间的差值}if(p[i].se){--p[i].se;q2.push({-x,i});}}else{//老鼠int kINT_MAX;//先将k定义为一个超出1e9范围的数如果外面没洞的话优先考虑这只老鼠if(!q2.empty()){//外面有洞int jq2.top().se;kxq2.top().fi;//k为洞和老鼠位置的差值q2.pop();if(p[j].se){--p[j].se;q2.push({-p[j].fi,j});}}ansk;//加上差值q1.push(-k-x);//存入-k-x具体看上面}}cout ans endl;return ;
}
