牛客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 ;
}