本文主要是介绍洛谷 3845 球赛#二分#，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
H发现小 H 不仅认真的记录了每一场比赛的最终比分，还把一些比赛的中间比分也记录下来，而更糟糕的是，小 H 并没有区分比赛的两个队。请问H至少错过了多少场比赛。注意小 H 记录的比分是没有先后顺序的。
分析
由于比分谁也不知道，所以可以把它们排序，最小值和最大值分别排序（贪心，离散），然后用最小值来一遍最长不下降子序列，dp。
代码
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
struct record{int a,b;}rec[1001]; int x,y,t,n,f[1001],ans;
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
bool cmp(record x,record y){return x.b<y.b||(x.b==y.b&&x.a<y.a);}
int main(){t=in();while (t--){memset(f,0,sizeof(f)); memset(rec,0,sizeof(rec)); n=in();for (int i=1;i<=n;i++){x=in(); y=in(); rec[i].a=min(x,y);rec[i].b=max(x,y);}stable_sort(rec+1,rec+1+n,cmp); ans=1; f[1]=rec[1].a;//排序for (int i=2;i<=n;i++){int k=0;for (int j=1;j<=ans;j++)if (rec[i].a>=f[j]&&f[k]<=f[j]) k=j;//找出最大且不小于最小比分的比分if (!k) f[++ans]=rec[i].a; else f[k]=rec[i].a;//找不到是新的一轮比赛，否则就插入。}printf("%d\n",ans);}return 0;
}
这篇关于洛谷 3845 球赛#二分#的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
