石岩做网站的公司,WordPress 摘要代码,广州线上教学,做网站空间哪个好正题
题目链接:https://www.luogu.com.cn/problem/P7514 题目大意
给出nnn个卡牌有ai/bia_i/b_iai/bi#xff0c;开始都是aia_iai朝上#xff0c;将不超过mmm张卡牌变为bib_ibi面朝上#xff0c;使得朝上的数字中最大值减去最小值最小。 3≤n≤106,1≤mn,1≤a…正题
题目链接:https://www.luogu.com.cn/problem/P7514 题目大意
给出nnn个卡牌有ai/bia_i/b_iai/bi开始都是aia_iai朝上将不超过mmm张卡牌变为bib_ibi面朝上使得朝上的数字中最大值减去最小值最小。
3≤n≤106,1≤mn,1≤ai,bi≤1093\leq n\leq 10^6,1\leq mn,1\leq a_i,b_i\leq 10^93≤n≤106,1≤mn,1≤ai,bi≤109 解题思路
虽然数据比较水但是题目也是一道比较水的贪心题。
先离散化然后考虑暴力点的想法。枚举最大值和最小值l,rl,rl,r那么对于aia_iai在[l,r][l,r][l,r]之间的自然是不理在之外的一定需要翻如果翻转后存在bib_ibi不在[l,r][l,r][l,r]之间那么显然行不通。
这样我们就可以O(n2)O(n^2)O(n2)了。
不难发现假设[l,r][l,r][l,r]行的通那么[l,r1][l,r1][l,r1]用原来的方法一定也行得通所以对于rrr递增lll也是不降的双指针维护一下就好了。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includecctype
using namespace std;
const int N2e610;
int n,m,ans,a[N],b[N],c[N],mx[N],mi[N],nx[N],ni[N],pos[N];
int read(){int x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
bool cmp(int x,int y)
{return a[x]a[y];}
bool check(int l,int r){int Lpos[l],Rpos[r1]-1;int km-(n-R)-(L-1);if(k0)return 0;if(mx[L-1]r||mi[L-1]l)return 0;if(nx[R1]r||ni[R1]l)return 0;return 1;
}
int main()
{nread();mread();for(int i1;i2*n;i)a[i]b[i]read(),c[i]i;sort(c1,c12*n,cmp);int cnt2*n;for(int i1;i2*n;i)a[c[i]]i;mi[0]ni[n1]1e97;for(int i1;in;i)mx[i]max(a[in],mx[i-1]);for(int i1;in;i)mi[i]min(a[in],mi[i-1]);for(int in;i1;i--)nx[i]max(a[in],nx[i1]);for(int in;i1;i--)ni[i]min(a[in],ni[i1]);for(int i1;in;i)pos[a[i]]i;pos[cnt1]n1;for(int icnt;i1;i--)if(!pos[i])pos[i]pos[i1];ans1e97;int z0;for(int i1;icnt;i){while(zicheck(z1,i))z;if(z)ansmin(ans,b[c[i]]-b[c[z]]);}printf(%d\n,ans);
}
