https://codeforces.com/contest/1257/problem/E
题意：有三个集合集合里面的数字可以随意变换位置，不同集合的数字，如从第一个A集合取一个数字到B集合那操作数+1，求最少操作次数使得一二三集合连起来是升序
我们先把每个集合排个序，然后拼起来，求一遍lis（最长升序序列：https://blog.csdn.net/Joined/article/details/78058362），然后n-len即为答案
网上那些什么dp什么的。。嘻嘻太高深
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
int k1,k2,k3,n,a[maxn],dp[maxn],b[maxn],len;
void lis(){
len=1;b[1]=a[0];
for(int i=1;i<n;i++){
b[len+1]=n+1;
int l=0,r=len+1,ans=0;
while(l<=r){
int mid=(l+r)/2;
if(a[i]<b[mid]){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
b[ans]=a[i];
if(ans>len)len++;
}
cout<<n-len<<endl;
}
int main(){
scanf("%d%d%d",&k1,&k2,&k3);
n=k1+k2+k3;
for(int i=0;i<k1+k2+k3;i++){
scanf("%d",&a[i]);
}
sort(a,a+k1);
sort(a+k1,a+k1+k2);
sort(a+k1+k2,a+k1+k2+k3);
lis();
}
https://codeforces.com/contest/1257/problem/D
赛后才想出来的一道题：
题意大概是，给你一串怪物，怪物有攻击力，你有几个英雄，每个英雄有攻击力和耐力，攻击力大于怪物的你就击败一个怪物，但耐力减少一，改天结束的条件是，改英雄耐力耗完或者是改英雄攻击力打不过怪物无奈退出，每天可安排一个英雄，英雄可多次使用，至少多少天清楚掉这些怪物。
很容易想到二分找到一个大于该怪物的的英雄，贪心选取最优的一个。
思路：我们先排序
bool cmp(node A,node B)
{
if (A.pi!=B.pi) return A.pi<B.pi;
return A.si>B.si;
}
排完序后，我们要对这些英雄进行优化，为什么要优化呢？因为我们的思路为以下
遇到第一个怪物然后二分查找第一个英雄，然后枚举怪物，英雄遇到一个打不过的，我们往后找，英雄战力是递增的嘛，而且我们希望找到的是英雄更大耐力也更大的吧，你肯定不想找耐力反而更少的，浪费时间。
所以我们的优化有两个，第一出现相同战力的英雄经过我们上面的排序，剔除掉耐力低的。
第二，由于我们的战力从小排到大，出现战力大于a，耐力又大于a的b，肯定是直接舍弃a，经过这些筛选，就减少了不必要的枚举。
接下来就可以开始枚举了
#include <bits/stdc++.h>
#define N 200010
using namespace std;
int res,len,now,now2,tmp,maxx;
int read(){
char c=getchar();int x=0,f=1;
while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();}
while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();}
return x*f;
}
struct node{
int pi,si;
}b[N];
int n,tmpp;
int a[N];
bool cmp(node A,node B)
{
if (A.pi!=B.pi) return A.pi<B.pi;
return A.si>B.si;
}
inline erfen(int x)
{
int l=1,r=tmpp,mid,t;
while (l<=r){
mid=(l+r)/2;
if (x==b[mid].pi) return mid;
if (x<b[mid].pi) r=mid-1,t=mid;
else l=mid+1;
}
return t;
}
int main()
{
// freopen("t.txt","r",stdin);
int m;
int T=read();
while (T--)
{
n=read();
maxx=0;
for(int i=1;i<=n;i++)
a[i]=read(),maxx=max(maxx,a[i]);
m=read();
for (int i=1;i<=m;i++)
b[i].pi=read(),b[i].si=read();
sort(b+1,b+m+1,cmp);
if(maxx>b[m].pi){
puts("-1");
continue;
}
tmp=1;
for(int i=2;i<=m;i++)
if(b[i].pi!=b[tmp].pi) b[++tmp]=b[i];
tmpp=tmp;
tmp=1;
for(int i=2;i<=tmpp;i++)
{
while (b[i].si>=b[tmp].si&&tmp>0) tmp--;
b[++tmp]=b[i];
}
tmpp=tmp;
res=0;
now=1;
while(now<=n)
{
len=1;
now2=erfen(a[now]);
while(b[now2].si>len){
if(a[now+1]<=b[now2].pi) now++,len++;
else{
while(a[now+1]>b[now2].pi&&len+1<=b[now2].si) now2++;
if(a[now+1]>b[now2].pi||len+1>b[now2].si) break;
now++;len++;
}
}
res++;
now++;
}
printf("%d\n",res);
}
}
原文：https://www.cnblogs.com/hgangang/p/11871685.html