牛客周赛 Round 82

当且仅当首尾相同
中间与首尾相同也可以

B,C唯一的区别就是对排序的时间复杂度要求不同
很经典的题

不同的窗口不能同时关闭，否则不能被拍照，而瞬移拍照不需要时间，所以只需要数组中能严格递增就行，然后需要排序，

C
排序的同时，携带每个元素在原数组中的位置
B

#include<bits/stdc++.h>

using namespace std;
int n;
const int maxn=1e3+10;

int a[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    sort(a+1,a+1+n);
    
    for(int i=1;i<n;++i){
        if(a[i+1]<=a[i]) {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
    return 0;
}

#include<bits/stdc++.h>

using namespace std;
int n;
const int maxn=2e5+10;

struct node{
    int p,val;
}a[maxn];
bool cmp(node a,node b){
    return a.val<b.val;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i].val,a[i].p=i;
    sort(a+1,a+1+n,cmp);
    
    for(int i=1;i<n;++i){
        if(a[i+1].val<=a[i].val) {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
    for(int i=1;i<=n;++i) cout<<a[i].p<<" ";
    return 0;
}

首先我们有两种不成立的情况容易想到

1. 末尾不是1，因为最后一个，最小的，最小的一定是1
2. pre一定是单调递减，因为不可能前i个数中的最小值大于前i-1个数的最小值

开始构造

• 对于pre[i]值在序列中第一次出现，第i个的值一定是pre[i]
• pre[i]在序列中重复出现，那么当前第i个位置，可以选的数是\(n-pre[i]-(i-2)\)
  • 我们来推导这个n-pre[i]-(i-2)
    1. n-pre[i]代表大于pre[i]可以选的数有多少个，当然不能超过n
    2. -(i-2)代表，首先已经有i-2个数已经不能被选，因为这些数是大于pre[i]的，而为什么不减去i-1，因为第i-1个数已经被固定

#include<bits/stdc++.h>

using namespace std;
#define ll long long 
int t;
int n;const int maxn=2e5+10;
int pre[maxn];
const int mod=998244353;
int a[maxn];
void solve(){
    cin>>n;bool book=0;
    for(int i=1;i<=n;++i){
        cin>>pre[i];
        if(i==1) continue;
        if(pre[i]>n-i+1 || pre[i]>pre[i-1]) book=1;
    }
    if(book){
        puts("0");
        return ;
    }
    ll ans=1;
    for(int i=2;i<=n;++i){
        if(pre[i]==pre[i-1]){
            int x=n-pre[i]-(i-2);
            if(x<=0){
                puts("0");
                return ;
            }
            ans=ans*x%mod;
        }
    }
    
    cout<<ans<<endl;    
}
int main(){
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

如果写过练习赛134的B题，你会很容易想到思路，完全可以借鉴

• 用一个数组记录a数组的前i项中m个数和的最小值
• 用一个数组记录b数组的后i项中m个数和的最小值

记录时，用一个优先队列，始终保持其中有m个数，往后取一个数如果比其中最大的数小，就踢出，并替换

根据题目条件，a选取最后一个数的下标不能比b数组选取的第一个数的下标更大
所以\(ans=min(ans,mina[i]+minb[i+1]);i \in [m,n-m]\)

#include<bits/stdc++.h>

using namespace std;
#define ll long long 
int n,m;
const int maxn=2e5+10;
int a[maxn],b[maxn];
ll mina[maxn],minb[maxn];
priority_queue<int>q;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i) cin>>b[i];
    ll sum=0;
    for(int i=1;i<=n-m;++i){
        if(i<=m){
            q.push(a[i]);
            sum+=a[i];
        }
        else {
            if(a[i]<q.top()){
	            sum-=q.top();
	            q.pop();
	            q.push(a[i]);
	            sum+=a[i];
			}
            
        }
        if(i>=m){
            mina[i]=sum;
        }
    }
    while(!q.empty()) q.pop();
    sum=0;
    for(int i=n;i>m;--i){
        if(n-i+1<=m){
            q.push(b[i]);
            sum+=b[i];
        }
        else {
            if(b[i]<q.top()) {
	            sum-=q.top();
	            q.pop();
	            q.push(b[i]);
	            sum+=b[i];
			}
            
        }
        if(n-i+1>=m){
            minb[i]=sum;
        }
    }
    ll ans=1e18;
    for(int i=m;i<=n-m;++i){
        ans=min(ans,mina[i]+minb[i+1]);
    }
    cout<<ans<<endl;
}