1148 B
题意
一个人要从出发点飞到A地，有 (n) 趟不同时间的航班；再从A地飞到B地，有 (m) 趟不同的航班。飞机飞行时间从起点到A需要 (t_a) ，从A到B需要 (t_b) 。现在你有 (k) 次机会能取消航班，请最大化这个人到B地的时间（到不了最好）。到不了输出 (-1) 。
Examples
input
4 5 1 1 2
1 3 5 7
1 2 3 9 10
output
11
input
2 2 4 4 2
1 10
10 20
output
-1
input
4 3 2 3 1
1 999999998 999999999 1000000000
3 4 1000000000
output
1000000003
解
two-pointers， (i) 指针枚举上面 (n) 趟航班，对于航班 (i) ， (j) 指针移动到人到达A地后最早的航班，然后计算。
细节多
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=200003;
const long long INFll=4500000000000000000ll;
long long a[maxn],b[maxn],ta,tb;
int n,m,k;
int main(){
scanf("%d%d%lld%lld%d",&n,&m,&ta,&tb,&k);
for(int i=1;i<=n;i++)scanf("%lld",a+i);
for(int i=1;i<=m;i++)scanf("%lld",b+i);
a[n+1]=INFll;
if(m<=k){puts("-1");return 0;}
int i=1,j=1,r=k;
for(;j<=m&&b[j]<a[1]+ta;j++);
if(j+k>m){puts("-1");return 0;}
long long ans=b[j+k]+tb;
for(;i<=n&&r>0;i++){
r--;
for(;j<=m&&b[j]<a[i+1]+ta;j++);
if(j+r>m){puts("-1");return 0;}
ans=max(ans,b[j+r]+tb);
}
printf("%lld
",ans<INFll?ans:-1ll);
return 0;
}
1148 C
题意
给你一个排列 (p) ，每次你可以 ( ext{swap}(p[i],p[j])(2*|i-j|≥n)) ，给出一种操作次数 (le 5*n) 的方案。肯定存在。
Examples
input
2
2 1
output
1
1 2
input
4
3 4 1 2
output
4
1 4
1 4
1 3
2 4
input
6
2 5 3 1 4 6
output
3
1 5
2 5
1 4
解
极其费时间的分类讨论题。
思路极其比较繁琐，看代码吧
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=300003;
typedef pair<int,int> P;
int n,a[maxn],pos[maxn];
vector<P> ANS;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",a+i),pos[a[i]]=i;
int x,y;
for(int i=1;i<=n;i++){
if(i==pos[i])continue;
if(abs(pos[i]-i)<n/2){
if(pos[i]<=n/2){
if(i<=n/2){
x=pos[i];
ANS.push_back(P(n,i));
swap(pos[a[n]],pos[a[i]]),swap(a[n],a[i]);
ANS.push_back(P(n,x));
swap(pos[i],pos[a[n]]),swap(a[n],a[x]);
ANS.push_back(P(n,i));
swap(pos[a[n]],pos[a[i]]),swap(a[n],a[i]);
}
else{
x=pos[i],y=i;
ANS.push_back(P(x,n));
swap(pos[a[x]],pos[a[n]]),swap(a[x],a[n]);
ANS.push_back(P(y,1));
swap(pos[a[y]],pos[a[1]]),swap(a[y],a[1]);
ANS.push_back(P(1,n));
swap(pos[a[1]],pos[a[n]]),swap(a[1],a[n]);
ANS.push_back(P(x,n));
swap(pos[a[x]],pos[a[n]]),swap(a[x],a[n]);
ANS.push_back(P(y,1));
swap(pos[a[y]],pos[a[1]]),swap(a[y],a[1]);
}
}
else{
if(i>n/2){
x=pos[i];
ANS.push_back(P(1,i));
swap(pos[a[1]],pos[a[i]]),swap(a[1],a[i]);
ANS.push_back(P(1,x));
swap(pos[i],pos[a[1]]),swap(a[1],a[x]);
ANS.push_back(P(1,i));
swap(pos[a[1]],pos[a[i]]),swap(a[1],a[i]);
}
else{
x=pos[i],y=i;
ANS.push_back(P(x,1));
swap(pos[a[x]],pos[a[1]]),swap(a[x],a[1]);
ANS.push_back(P(y,n));
swap(pos[a[y]],pos[a[n]]),swap(a[y],a[n]);
ANS.push_back(P(1,n));
swap(pos[a[1]],pos[a[n]]),swap(a[1],a[n]);
ANS.push_back(P(x,1));
swap(pos[a[x]],pos[a[1]]),swap(a[x],a[1]);
ANS.push_back(P(y,n));
swap(pos[a[y]],pos[a[n]]),swap(a[y],a[n]);
}
}
}
else{
ANS.push_back(P(pos[i],i));
x=pos[i];
swap(pos[i],pos[a[i]]),swap(a[x],a[i]);
}
}
printf("%d
",int(ANS.size()));
for(int i=0;i<int(ANS.size());i++)printf("%d %d
",ANS[i].first,ANS[i].second);
return 0;
}
1148 D
题意
给你一个pair<int,int>数组 (a) ，长为 (n) ，现在你要确定一个排列 (p) ，使得数列 ((a[p_1].first,a[p_1].second,a[p_2].first,a[p_2].second,...,a[p_m].first,a[p_m].second)) 中的元素呈一大一小交错排列。保证 (a) 中的元素各不相同。
Examples
input
5
1 7
6 4
2 10
9 8
3 5
output
3
1 5 3
input
3
5 4
3 2
6 1
output
3
3 2 1
解
把 (first<second) 的归为一类， (first>second) 的归为一类，再分别排序、贪心选取，最后比较哪种方案更优。
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=300003;
struct P{
int first,second,num;
P(){}
P(int _1,int _2,int _3):first(_1),second(_2),num(_3){}
};
int n,cnt1,cnt2,vis[maxn],RES1[maxn],CNTRES1,RES2[maxn],CNTRES2;
P a[maxn],b[maxn],c[maxn],d[maxn];
int main(){
scanf("%d",&n);
for(int i=1,x,y;i<=n;i++){
scanf("%d%d",&x,&y);
if(x<y)cnt1++,a[cnt1]=b[cnt1]=P(x,y,i);
else cnt2++,c[cnt2]=d[cnt2]=P(x,y,i);
}
sort(a+1,a+cnt1+1,[](P x,P y){return x.first<y.first;});
sort(b+1,b+cnt1+1,[](P x,P y){return x.second<y.second;});
sort(c+1,c+cnt2+1,[](P x,P y){return x.first<y.first;});
sort(d+1,d+cnt2+1,[](P x,P y){return x.second<y.second;});
for(int i=cnt1,j=cnt1;;i--){
for(;i>=1&&vis[b[i].num];i--);
if(i==0)break;
vis[b[i].num]=1;
RES1[++CNTRES1]=b[i].num;
for(;j>=1&&(vis[a[j].num]||b[i].second<a[j].first);j--);
if(j==0)break;
vis[a[j].num]=1;
RES1[++CNTRES1]=a[j].num;
}
for(int i=1;i<=n;i++)vis[i]=0;
for(int i=1,j=1;;i++){
for(;i<=cnt2&&vis[d[i].num];i++);
if(i>cnt2)break;
vis[d[i].num]=1;
RES2[++CNTRES2]=d[i].num;
for(;j<=cnt2&&(vis[c[j].num]||d[i].second>c[j].first);j++);
if(j>cnt2)break;
vis[c[j].num]=1;
RES2[++CNTRES2]=c[j].num;
}
if(CNTRES1<CNTRES2)swap(CNTRES1,CNTRES2),swap(RES1,RES2);
printf("%d
",CNTRES1);
for(int i=1;i<=CNTRES1;i++)printf("%d ",RES1[i]);
return 0;
}
1148 E
题意
数组 (a) （输入给定），每次你可以使得 (a) 中的两个元素更靠近（例： (1,3→2,2) ， (3,100→50,63) ）使得数组 (a) 元素组成的multiset和数组 (b) （输入给定）组成的multiset相同，现在要你给出一种方案，次数 (le 5*n) 。
Examples
input
5
2 2 7 4 9
5 4 5 5 5
output
YES
4
4 3 1
2 3 1
2 5 2
1 5 2
input
3
1 5 10
3 5 7
output
NO
input
4
1 4 5 8
2 3 6 7
output
YES
2
1 2 1
3 4 1
解
先对 (a,b) 排序
从左往右扫， (val[i]) 表示 (a[i]) 还需要加多少。
用单调栈维护 (val[])
Code
#include<bits/stdc++.h>
using namespace std;
typedef pair<long long,int> P;
const int maxn=300003;
int n,stk[maxn],CNT;
long long b[maxn],val[maxn],ANS[maxn*5][3];
P a[maxn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i].first),a[i].second=i;
for(int i=1;i<=n;i++)scanf("%lld",b+i);
sort(a+1,a+n+1);
sort(b+1,b+n+1);
for(int i=1,top=0;i<=n;i++){
val[i]=val[stk[top]]+b[i]-a[i].first;
while(top&&val[i]<val[stk[top]]&&val[i]<=val[stk[top-1]]){
if(val[stk[top]]>val[stk[top-1]]){
ANS[++CNT][0]=a[stk[top]].second,ANS[CNT][1]=a[i].second,ANS[CNT][2]=val[stk[top]]-val[stk[top-1]];
a[stk[top]].first+=ANS[CNT][2],a[i].first-=ANS[CNT][2];
}
top--;
}
if(top&&val[i]<val[stk[top]]){
ANS[++CNT][0]=a[stk[top]].second,ANS[CNT][1]=a[i].second,ANS[CNT][2]=val[stk[top]]-val[i];
a[stk[top]].first+=ANS[CNT][2],a[i].first-=ANS[CNT][2];
val[stk[top]]=val[i];
}
stk[++top]=i;
}
for(int i=1;i<=n;i++)if(a[i].first!=b[i]){puts("NO");return 0;}
for(int i=1;i<=CNT;i++)if(ANS[i][2]<0){puts("NO");return 0;}
printf("YES
%d
",CNT);
for(int i=1;i<=CNT;i++)printf("%lld %lld %lld
",ANS[i][0],ANS[i][1],ANS[i][2]);
return 0;
}