建筑设计门户网站,大连网站建设方案咨询,自豪地使用wordpress,惠州抖音seo[LG P2519][BZOJ2298][HAOI2011]problem a
题目描述
一次考试共有n个人参加
第i个人说#xff1a;有ai个人分数比我高#xff0c;bi个人分数比我低。
问最少有几个人没有说真话(可能有相同的分数)
输入输出格式
输入格式#xff1a;
第一行一个整数n有ai个人分数比我高bi个人分数比我低。
问最少有几个人没有说真话(可能有相同的分数)
输入输出格式
输入格式
第一行一个整数n接下来n行每行两个整数第i1行的两个整数分别代表ai、bi
输出格式
一个整数表示最少有几个人说谎
输入输出样例
输入样例#1
3
2 0
0 2
2 2
输出样例#1
1
说明
1≤n≤100000 0≤ai、bi≤n Solution
只要想到一点此题就很简单了
有个人比我高个人比我低意味着个人与我相同分数
也就是说排名为的人的分数相同。 其中有两种必定为假的情况
。同样说这句话的人超过了个。去除这些之后就只剩下一堆合法的区间 让你选择每个区间的价值为说这句话的人数当然价值最大为区间长度且需满足任意两个选取的区间没有公共点。
于是问题变成了选取最大价值和的不相交区间。 这时只需要按区间右端点排序直接DP二分答案求解答案即可相信看懂题目和前面步骤的人都会这一步另外感觉这里的DP只是一个贪心而已。。。。
#includebits/stdc.h
using namespace std;
const int MAXN1e5500;
int f[MAXN];
struct snode{int l,r;} score[MAXN];
struct qnode{int l,r,num; } q[MAXN];
int compare1(snode x,snode y){ return x.ly.l||(x.ly.lx.ry.r); }
int compare2(qnode x,qnode y){ return x.ry.r||(x.ry.rx.ly.l); }
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
int find(int x,int n)
{int l0,rn;while (lr){int mid(lr1)1;if (q[mid].rx) lmid;else rmid-1;}return l;
}
int main()
{int nread(),cnt0;for (int i1;in;i) score[i].lread()1,score[i].rn-read();sort(score1,scoren1,compare1);for (int i1;in;i){if (score[i].lscore[i].r) continue;if (score[i].lscore[i-1].lscore[i].rscore[i-1].r) q[cnt].num;else q[cnt]{(qnode){score[i].l,score[i].r,1}};}sort(q1,qcnt1,compare2);for (int i1;icnt;i){int kfind(q[i].l,cnt); f[i]max(f[i-1],f[k]min(q[i].num,q[i].r-q[i].l1));}printf(%d\n,n-f[cnt]);return 0;
}
