牛客14666(优先屏障) + 牛客14847(Masha与老鼠)
写在前面
昨天刷的这两道题写了很久·····，特别是Masha与老鼠这道题，写了都快3个小时，主要还是理解代码逻辑有点难，不过写完之后感觉收获挺大的，给我以后刷题提供很好的思路
14666-优先屏障
思路
考点：单调栈+前缀后缀模拟
我们先不考虑屏障的位置，先考虑某个点往前面看和往后面看监视的总个数，很容易想到前缀和后缀的思路，在此之前先说栈的用处，栈用来存放每次遍历过的山的高度，先说前缀的思路，从头遍历，每次先加上前面监视的个数，判断当前栈顶元素是否小于当前元素，如果小于将栈顶排除，计数器+1（如果当前元素的高度大于栈顶元素，那么之后的山都看不到栈顶元素的山，所以直接将他排出去），如果栈为空，加上计数器，反之加上计数器的同时在+1（当前的山和栈顶的山可以相互监视），然后再将当前元素进栈，后缀同理，然后再从头遍历，由于加完屏障左边的只能看前面，右边的只能看后面，所以考虑前缀[i-1]和后缀[i]相加最小值即可
编程
const int N=5e4+5;
int a[N],qz[N],hz[N];
int num=1;
void solve(){
memset(hz,0,sizeof hz);
stack<int> st;
int n;cin >> n;
for(int i=1;i<=n;++i) cin >> a[i];
for(int i=1;i<=n;++i){
int sum=0;
qz[i]=qz[i-1];
while(!st.empty() && st.top()<a[i]){//判断是否需要排除栈顶元素
sum++;
st.pop();
}
if(st.empty()) qz[i]+=sum;//栈为空加上计数器
else qz[i]+=sum+1;//不为空加上计数器在加上本身
st.push(a[i]);
}
while(!st.empty()) st.pop();
for(int i=n;i>=1;--i){
int sum=0;
hz[i]=hz[i+1];
while(!st.empty() && st.top()<a[i]){
sum++;
st.pop();
}
if(st.empty()) hz[i]+=sum;
else hz[i]+=sum+1;
st.push(a[i]);
}
int maxn=0,k=0;
int mx=qz[n];//总的监视个数
for(int i=1;i<=n;++i){
if(mx-(qz[i-1]+hz[i])>maxn){//前缀和后缀相加的值最小
maxn=mx-(qz[i-1]+hz[i]);
k=i;
}
}
cout << "Case #" << num++ << ": " << k << " " << maxn << endl;
return ;
}
14847-Masha与老鼠
思路
考点：贪心+反悔贪心
根据贪心策略，每只老鼠有两个选择，左边最近的有容量的洞，右边最近的有容量的洞
- 优先队列q1存老鼠，q2存洞，按坐标大小出队。老鼠存的值为-k-x，洞存的值为-x，x为该点坐标，k为偏差值。
输入一个洞-鼠-洞-鼠-洞样例，仔细观察。当鼠2进洞2时，鼠1的位置被挤掉，那么鼠1就会回到上一个状态，k值算的就是所有现状态回到上一个状态时的偏差值的累加，即ans += k，就能让ans回到上一个状态。
讲起来比较抽象，具体看代码
编程
const int N=2e6+50;
PII p[N];
priority_queue<int,vector<int>,greater<int>> q1;//存老鼠
priority_queue<PII,vector<PII>,greater<PII>> q2;//存洞，用pair存洞的位置和下标
void solve(){
int n,m;
cin >> n >> m;
int sum=n;
int ans=0;
for(int i=1;i<=n;++i) cin >> p[i].fi;
for(int i=1;i<=m;++i){
cin >> p[i+n].fi >> p[i+n].se;
sum-=p[i+n].se;
}
n+=m;
if(sum>0){//无解只要判断洞的总数小于老鼠总数即可
cout << -1 << endl;
return ;
}
sort(p+1,p+1+n);//将老鼠和洞的位置按升序排序
for(int i=1;i<=n;++i){
int x=p[i].fi;
if(p[i].se){//洞
while(p[i].se && !q1.empty() && x+q1.top()<0){//将q1.top展开，x1-x2<k,意思为当前坐标减去老鼠坐标小于之前他们的差值
int k=x+q1.top();
ans+=k;//加上差值
q1.pop();
--p[i].se;
q2.push({-k-x,0});//提供反悔次数，如果后边的老鼠进入当前这个洞，则会将当前老鼠挤回前面那个洞，这里-k为这个老鼠进入这个洞和进入前面那个洞之间的差值
}
if(p[i].se){
--p[i].se;
q2.push({-x,i});
}
}
else{//老鼠
int k=INT_MAX;//先将k定义为一个超出1e9范围的数，如果外面没洞的话优先考虑这只老鼠
if(!q2.empty()){//外面有洞
int j=q2.top().se;
k=x+q2.top().fi;//k为洞和老鼠位置的差值
q2.pop();
if(p[j].se){
--p[j].se;
q2.push({-p[j].fi,j});
}
}
ans+=k;//加上差值
q1.push(-k-x);//存入-k-x具体看上面
}
}
cout << ans << endl;
return ;
}
原文地址：https://blog.csdn.net/wh233z/article/details/140625359
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！