description

一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)

analysis

这题转化模型很妙，容易知道最少没有说真话的数量\(=n-\)说真话最多的数量
对于\(a_i\)个比\(i\)大、\(b_i\)个比\(i\)小，可以看成\(i\)分数排名第\(a_i+1\)名
又由于有重分，那么转化成\([a_i+1,n-b_i]\)这段排名内的分数全部相等
判断某个区间单独不可行就判断\(a_i+1\)是否大于\(n-b_i\)
如果两个区间有交（且不完全重合），这肯定不合法，至少一个是假话
这是因为给出的分数区间唯一确定，不可能出现同分数不同区间
现在问题相当于有很多条线段，求\([1,n]\)区间内，最大线段个数覆盖是多少
先把线段按右端点排序，然后统计同一区间出现的次数，次数大于区间长度则取\(min\)
设\(f[i]\)表示到第\(1\)位到第\(i\)位最大线段覆盖，由于排序好了，维护一个左端点转移
若\(b[left].y==i\)，则可以转移到\(f[i]\)，\(++left\)继续转移即可
我调了很久因为\(n\)前后不一样，实际应该取最初读入的\(n\)来算答案

code

#pragma GCC optimize("O3")

#pragma G++ optimize("O3")

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define MAXN 100005

#define ll long long

#define reg register ll

#define fo(i,a,b) for (reg i=a;i<=b;++i)

#define fd(i,a,b) for (reg i=a;i>=b;--i)

using namespace std;

ll f[MAXN],val[MAXN];

ll n,m,tot,cnt;

struct node

{

	ll x,y;

}a[MAXN],b[MAXN];

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}

	while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*f;

}

inline bool cmp(node a,node b){return a.y<b.y || (a.y==b.y && a.x<b.x);}

int main()

{

	//freopen("P2519.in","r",stdin);

	n=m=read();

	fo(i,1,n)

	{

		ll x=read(),y=read();

		if (x+y>=n)continue;

		a[++tot].x=x+1,a[tot].y=n-y;

	}

	n=tot,tot=0,sort(a+1,a+n+1,cmp);

	fo(i,1,n)

	{

		if (i>1 && a[i].x==a[i-1].x && a[i].y==a[i-1].y){++val[tot];continue;}

		b[++tot]=a[i],val[tot]=1;

	}

	fo(i,1,tot)val[i]=min(val[i],b[i].y-b[i].x+1);

	ll left=0;memset(f,128,sizeof(f)),f[0]=0;

	fo(i,1,m)

	{

		f[i]=f[i-1];

		while (left<tot && b[left+1].y==i)++left,f[i]=max(f[i],f[b[left].x-1]+val[left]);

	}

	printf("%lld\n",m-f[m]);

	return 0;

}

巴特西

【BZOJ2298】【luoguP2519】problem a

description

analysis

code

最新文章

热门文章