首页 > 代码库 > 同花顺
同花顺
洛谷P2652 同花顺
这是在2017日照夏令营的D1T2，我认为质量相当高的一道题，第一次在赛场上做的时候爆零了，当时态度不很端正，暴力不想打，想投机取巧骗分，还是不要把希望压在不确定的事情上，有多少分实实在在拿着就拿着，然后能力之外的再尽可能获得更多。言归正传，这个用类似枚举的思路来做，枚举一个同花顺的左右端点，具体是外循环先确定j，然后枚举可能的第一个左端点，然后用n-max（ans）；这个的证明是向李子晗学习的，回来后我又在洛谷上做了一遍，50分。接下来是核心部分：先说我为什么是错的，我的i，j中间是连续的递增+1的同花顺，然后这一部分不用换，n-最大的连续序列就是答案，但正解是a[右端点].num-a[左端点].num+1<=n;
证明如下：
j i
| | | | |
这是i和j确定的序列，满足上面那个条件j就左移，为什么呢？因为要保证i，j内的序列是连续递增的（在换完之后），现在只要证明它能换完就可以了，如果a[右端点].num-a[左端点].num+1<=n
，那就是说序列总长度最多为n，好了，现在我们有n个数，那怎么换都能换到+1 递增上去，空缺就都能补上，i，j之间的都不用动，所以求最大的i，j之外的数的个数就好了。
注：今天向苗若桐学习了结构体重载运算符，会用了unique函数。
#include<bits/stdc++.h> using namespace std; struct node { int color; int num; bool operator < (const node &a)const { if(color==a.color) return num<a.num; return color<a.color; } bool operator == (const node &a)const { return num==a.num&&color==a.color; } bool operator != (const node &a)const { return !(*this==a); } }a[100001]; int n; int ans; void Cin(int &x) { char c=getchar();x=0; while(c>‘9‘||c<‘0‘) c=getchar(); while(c<=‘9‘&&c>=‘0‘) x=x*10+c-‘0‘,c=getchar(); } int main() { cin>>n; int i; for(i=1;i<=n;i++) Cin(a[i].color),Cin(a[i].num); sort(a+1,a+n+1); int from=1,to=1; int l=unique(a+1,a+n+1)-a; int maxn=0; for(i=1;i<l;i++) { for(int j=i;i>=1;j--) { if(a[i].color==a[j].color&&a[i].num-a[j].num+1<=n) maxn++; else break; } ans=max(ans,maxn); maxn=0; } cout<<n-ans; return 0; }
同花顺
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。