div3部分

Round #653 E.Reading Books

题意

Alice和Bob一起从n本书中选择若干本进行阅读,这些书当中ai=1的是Alice喜欢的,bi=1的是Bob喜欢的,可以两个人同时喜欢也可以同时不喜欢,至少让每个人都阅读到k本喜欢的书,求需要花的最短时间是多久。

思路

很明显两个人都不喜欢的书在这时候是没有作用的,也就是一定不会选。将剩下的书分为三堆,用一个set数组bo(book)来存储看每本书需要花的时间,从小到大遍历,如果当前两个人都喜欢的那堆书中需要花时间最小的书小于另外两堆最小时间的和,则从两个人都喜欢的书堆中选取,否则从另外两个书堆中分别取最省时的那一本,直到满足k为止。当然如果某一堆已经空了,则不能从当前堆种选取,如果最后没有满足k本书,那么显然是无解的,输出-1。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+10;
const int inf=0x3f3f3f3f;
vector<int>bo[4];
main() {
        int n,k;
        cin>>n>>k;
        for(int i=0;i<n;++i){
            int a,b,t;
            scanf("%lld%lld%lld",&t,&a,&b);
            bo[a*2+b].emplace_back(t);
        }
        sort(bo[1].begin(),bo[1].end());
        sort(bo[2].begin(),bo[2].end());
        sort(bo[3].begin(),bo[3].end());
        int pos=0;
        int pos1=0;
        int ans=0;
        while(k){
            if(pos<min(bo[1].size(),bo[2].size())){
            if(pos1<bo[3].size()&&bo[3][pos1]<bo[1][pos]+bo[2][pos]){
                ans+=bo[3][pos1];
                pos1++;
                k--;
            }else {
                ans+=bo[1][pos]+bo[2][pos];
                pos++;
                k--;
            }
            }else if(pos1<bo[3].size()) {
                ans+=bo[3][pos1];
                pos1++;
                k--;
            }else break;
        }
        if(k)puts("-1");
        else cout<<ans<<endl;
}

思路

相比于上一题,这题多了一个限制要求,即使能选取的书本总数不再是若干本,而是从n本书中选取m本,其他地方与上一题无异。

那么这时候两人都不喜欢的书不再是没用的了,比方说已经选好了能够满足k的小于m本书,还需要一定数量的书来充数,那么如果两人都不喜欢的书在剩下的书中所需的时间最小,就需要选取。这道题的关键在于寻找一个约束关系,既是选择两人共同喜欢的书本的数量是受到限制的,首先假设这个数量为cnt,那么为了满足k,仍然需要k-cnt本Alice喜欢的书和k-cnt本Bob喜欢的书,书的总数是cnt+2(k-cnt),而总数需要满足小于等于m本,也就是cnt+2(k-cnt)<=m,另外k-cnt也不能超出各自书堆的容量上限,也就是bo[2].size()>=k-cnt,bo[1].size()>=k-cnt。在这样的情况下对cnt进行枚举,若满足条件的cnt的数量大于bo[3].size(),那么显然不存在任何一种解使命题成立,输出-1即可。

在对cnt进行枚举操作时,只需要逐步增加cnt的数量,这样做的结果是“必须”的书本数量会减少,因为可以视作将需要的两本书合作了一本,在确定好“必须”的构成情况后,就只需要贪心地从两人都喜欢的书堆中选择cnt本所需时间最小的书,从两个各自喜欢的书堆中分别选取k-cnt本所需时间最小的书,再从剩下的书中选择所需时间最小的书,使总共选取的书的本数达到m本,记一个所有情况的最小值即是答案。题目要求给出所选书的编号,那么在确定cnt的情况下再选取一遍存在vector里输出即可。

ps.整体操作还是比较繁琐的,我花了很久交了10发才通过

代码

#include<bits/stdc++.h>
using namespace std;
const int inf=2e9+1;
void upd(int need,set<pair<int,int>> &fr,set<pair<int,int>> &st,int &stsum){
    need=max(need,0);
    while(true){
        bool flag=true;
        while(need>st.size()&&!fr.empty()){
            stsum+=fr.begin()->first;
            st.insert(*fr.begin());
            fr.erase(fr.begin());
            flag=false;
        }
        while(need<st.size()){
            stsum-=st.rbegin()->first;
            fr.insert(*st.rbegin());
            st.erase(prev(st.end()));
            flag=false;
        }
        while(!fr.empty()&&!st.empty()&&fr.begin()->first<st.rbegin()->first){
            stsum-=st.rbegin()->first;
            stsum+=fr.begin()->first;
            fr.insert(*st.rbegin());
            st.erase(prev(st.end()));
            st.insert(*fr.begin());
            fr.erase(fr.begin());
            flag=false;
        }
        if(flag)break;
    }
}
int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    vector<pair<int,int>>all[4];
    for(int i=0;i<n;++i){
        int t,x,y;
        scanf("%d%d%d",&t,&x,&y);
        all[2*x+y].push_back({t,i+1});
    }
    set<pair<int,int>>st;
    set<pair<int,int>>fr;
    int cnt=0;
    while(cnt+2*(k-cnt)>m||k-cnt>all[1].size()||k-cnt>all[2].size()){
        cnt++;
    }
    if(cnt>all[3].size())puts("-1");
    else{
        vector<int>sum[4];
        for(int i=0;i<4;++i){
            sort(all[i].begin(),all[i].end());
            sum[i].push_back(0);
            for(int j=0;j<all[i].size();++j){
                sum[i].push_back(sum[i].back()+all[i][j].first);
            }
        }
        for(int i=0;i<all[0].size();++i)
            fr.insert(all[0][i]);
        for(int i=1;i<=2;++i)
            for(int j=k-cnt;j<all[i].size();++j)
                fr.insert(all[i][j]);
        int need=m-cnt-2*(k-cnt);
        int stsum=0;
        upd(need,fr,st,stsum);
        int ans=inf;
        int pos;
        for(int i=cnt;i<=all[3].size();++i){
            if(i>=k){
                int tmp;
                tmp=sum[3][i]+stsum;
                if(i+st.size()==m&&tmp<ans){
                    ans=tmp;
                    pos=i;
                }
            }else{
                int tmp;
                tmp=sum[3][i]+sum[1][k-i]+sum[2][k-i]+stsum;
                if(i+(k-i)*2+st.size()==m&&tmp<ans){
                    ans=tmp;
                    pos=i;
                }
            }
            if(i>=k)need--;
            else {
                need++;
                fr.insert(all[1][k-i-1]);
                fr.insert(all[2][k-i-1]);
            }
            upd(need,fr,st,stsum);
        }
        need=m-cnt-2*(k-cnt);
        st.clear();
        fr.clear();
        for(int i=0;i<all[0].size();++i)
            fr.insert(all[0][i]);
        for(int i=1;i<=2;++i)
            for(int j=k-cnt;j<all[i].size();++j)
                fr.insert(all[i][j]);
        stsum=0;
        upd(need,fr,st,stsum);
        for(int i=cnt;i<=pos;++i){
            if(i==pos)break;
            if(i>=k)need--;
            else {
                need++;
                fr.insert(all[1][k-i-1]);
                fr.insert(all[2][k-i-1]);
            }
            upd(need,fr,st,stsum);
        }
        printf("%d\n",ans);
        for(int i=0;i<pos;++i)
            printf("%d ",all[3][i].second);
        for(int i=0;i<k-pos;++i)
            for(int j=1;j<=2;++j)
                printf("%d ",all[j][i].second);
        for(auto i:st)
            printf("%d ",i.second);
        puts("");
    }
}

Round #653 F. Cyclic Shifts Sorting

题意

将原始数列进行排序,排序方式是只能进行一种轮换操作,即abc->cab,要求在n2步内完成操作,并输出操作的左端的下标(从1开始),比方说有一个数列1573,那么在下标为2处进行一次轮换操作1573->1357,就算完成了排序。

思路

和冒泡排序完全相同的思路,从左至右遍历,即从a[0]到a[3],后两位长度不足无法操作,将三个数中最大的数换到最前面。这样最终得到的数组除了前两位没有排好序之外都已经从小到大排序,但是依然存在两个问题,即如果三个数中存在两个数一样大,那么排到最前面的只有其中之一,比方说下面这组数据3135,a[0]a[1]a[2]当中“最大”的3已经排在了最前面,那么程序便不会继续操作,最后的数组并不满足条件。这种情况只要加一个特判即可,如果a[0]=a[2],那么在a[0]处轮换两次就能得到正确的数列。另一种情况是如果最后的排序结果如下5177,这种情况下如果只是a[0]a[1]a[2]进行轮换显然是无法解决问题的,但是我们发现,只要在a[3],a[2]处分别进行一次轮换便能得到正确的数列,这是因为a[3]=a[2]导致的。

接下来探讨这种情况的普适性,假设有一个数列abcd,在2,1处分别进行一次操作,那么就会得到如下结果abcd->adbc->badc,可以发现a和b的位置交换了,而c和d的位置也交换了。如果有5个数,abcde,在3,2,1处分别进行一次操作,就可得到abcde->abecd->acbed->baced,可以发现,位置交换的只有ab和de,更加普遍一些,一个任意长度的数列(n>=4),从n-2处一直操作到1处,最终交换的只有1,2和n,n-1,那么上面的问题就可以得到解决了,只要找到两个相同的数字,再从那两个数字一路操作到1,就可以交换a[0]和a[1]。

整体的操作不繁琐,冒泡排序也容易联想,就是最后一种操作比较难想。

代码

#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
const int N=2e5+5;
set<int>s;
int st[N],top;
pa a[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        cin>>n;
        int a[505];
        for(int i=1;i<=n;++i)cin>>a[i];
        vector<int>ans;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n-1-i;++j){
                int mx=0;
                int pos;
                for(int k=j;k<=j+2;++k){
                    if(a[k]>=mx){
                        mx=a[k];
                        pos=k-j;
                    }
                }
                if(pos==0){
                    ans.push_back(j);
                    ans.push_back(j);
                    int tmp=a[j+2];
                    a[j+2]=a[j];
                    a[j]=a[j+1];
                    a[j+1]=tmp;
                }else if(pos==1){
                    ans.push_back(j);
                    int tmp=a[j+2];
                    a[j+2]=a[j+1];
                    a[j+1]=a[j];
                    a[j]=tmp;
                }
            }
        }
        int f=0;
        if(a[1]==a[3]&&a[1]>a[2]){
            int tmp=a[2];
            a[1]=a[2];
            a[2]=a[3];
            ans.push_back(1);
            ans.push_back(1);
        }
        if(a[1]>a[2]){
            for(int i=n;i>=4;--i){
                if(a[i]==a[i-1]){
                    for(int j=i;j>=3;--j){
                        swap(a[j-2],a[j-1]);
                        swap(a[j],a[j-2]);
                        ans.push_back(j-2);
                    }
                    break;
                }
            }
        }
        //for(int i=1;i<=n;++i)cout<<a[i]<<" ";
        //cout<<endl;
        for(int i=1;i<=n-1;++i){
            if(a[i]>a[i+1]){
                f=1;
                break;
            }
        }
        if(f)cout<<"-1"<<endl;
        else{
            cout<<ans.size()<<endl;
            for(auto i:ans){
                cout<<i<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}

Round #650 F. Flying Sort

题意

思路

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
int a[maxn];
int dp[maxn];
main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        set<int>s;
        map<int,int>m;
        for(int i=1;i<=n;++i){
            dp[i]=0;
            cin>>a[i];
            s.insert(a[i]);
        }
        int tmp=1;
        for(auto i:s){
            m[i]=tmp++;
        }
        for(int i=1;i<=n;++i)a[i]=m[a[i]];
        for(int i=1;i<=n;++i){
            dp[a[i]]=max(dp[a[i]],dp[a[i]-1]+1);
        }
        int len=0;
        for(int i=1;i<=n;++i)len=max(len,dp[i]);
        cout<<n-len<<endl;
    }
}

思路

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
pair<int,int> a[maxn];
main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        set<int>s;
        for(int i=1;i<=n;++i){
            cin>>a[i].first;
            a[i].second=-i;
        }
        sort(a+1,a+n+1);
        vector<int>tmp;
        int ans=0;
        int l=1;
        for(int i=1;i<=n;++i){
            if(a[i].first!=a[i-tmp.size()].first){
                while(!tmp.empty()){
                    s.insert(*tmp.begin());
                    tmp.erase(tmp.begin());
                }
            }
            while(!s.empty()&&a[i].second>*s.begin()){
                s.erase(s.find(a[l++].second));
                //cout<<s.size()<<" "<<tmp.size()<<endl;
            }
            tmp.push_back(a[i].second);
            int tot=tmp.size()+s.size();
            ans=max(ans,tot);
        }
        cout<<n-ans<<endl;
    }
}
/**
100
5
3 5 8 1 7
**/

码字有点多...待填坑