时间戳

首页 > 技术文章 > 2020/5/26习题训练三

2020/5/26习题训练三

yy0826 2020-05-30 21:40 原文

A - Sorted Adjacent Differences

 题意：给一个数组，对他重新排序，使其相邻两数的差值不断递增

 题解：给数组从小到大排序，差值最小的是中间的两个数，然后再向两端延伸，能保证差值是增大的

            然后再根据n的奇偶性判断一下

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int a[100010];
int main(){
    int t,i,j;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(i=1;i<=n;i++){
            cin>>a[i];
        }
        sort(a+1,a+1+n);
        int front,back;
        if(n&1){
            front=n/2+1,back=n/2+2;
        }else{
            front=n/2,back=n/2+1;
        }
    
        while(front>=1||back<=n){
            if(front>=1){
                cout<<a[front]<<' ';
            }
            if(back<=n){
                cout<<a[back]<<' ';
            }
            back++,front--;
        }
        cout<<endl;
    }
        return 0;
}
View Code

B - Powered Addition

 题意：给数组，在第x秒可以对数组中任意元素加2x-1，求使数组变成非递减数列的最少秒数

题解：将数组变成递增数列，则数组任意位置的元素都比它前面最大的元素大，所以找前面最大的元素

             如果最大的元素比他小不用操作，比它大，求差值，找到所有差值里最大的，再求所需要的时间

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int a[100010];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,dff=0,maxx=0,sum=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        maxx=a[1];
        for(int i=1;i<=n;i++){
            maxx=max(a[i],maxx); //求的是a[i]前面最大的元素 
            if(a[i]<maxx)    // a[i]比前面最大的的元素小 
            dff=max(dff,maxx-a[i]);//求最大的差值 
        }
        if(dff==0){
            cout<<"0"<<endl;
        }else{
            for(int x=0;;x++){
                sum+=pow(2,x);
                if(sum>=dff){
                    cout<<x+1<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}
View Code

C - Middle Class

题意：政府认为财产大于等于X就是富人，给n个人的财富状况，政府可以从中选人，把这些人的财产平均一下

           求最多的富人数

题解：对这n个人的财富状况进行从大到小的排序，对前i个人的财富值求平均值，若平均值大于等于X，则这i个

           人可以变成富人，求最大的i

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll a[100010];
bool cmp(int a,int b){
    return a>b;
} 
int main(){
    int t;
    cin>>t;
    while(t--){
        ll n,x;
        ll item=0,counts,sum=0;
        cin>>n>>x;
        for(ll i=1;i<=n;i++){
            cin>>a[i];
        } 
        sort(a+1,a+1+n,cmp);
        if(a[1]<x){     //最大值小于X 没有富人 
            cout<<"0"<<endl;
        }else{
            counts=n;
            for(ll i=1;i<=n;i++){
                sum+=a[i];
                if(sum/i<x){
                    counts=i-1;
                    break;
                }
            }            
            cout<<counts<<endl;
        }


    }
        return 0;
}
View Code

D - Circle of Monsters

题意：有n个怪物围成一个圈，第i个怪物有a[i]滴血，每次射击是怪物血量减一，死后爆炸使第（i+1）怪物血量减b[i]，

          若第 (i+1) 个怪物也被炸死，也会对第（i+2）个怪物产生伤害，求使怪物全部死亡的最小射击数

题解：决定第一个射杀哪个怪物，剩下的要击杀的顺序就已经固定了，每个怪物死后会对下一个怪物造成伤害，若下

          一个怪物没死，即c[i]>0就要补枪，找第一个射杀的位置，使射击数最小

 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
#define maxn 300010
ll a[maxn],b[maxn],c[maxn];
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        ll n,i,j;
        ll minn=1e18,sum=0;
        cin>>n;
        for(i=1;i<=n;i++){
            cin>>a[i]>>b[i];
        }
        for(i=1;i<=n;i++){
            if(i==1){
                c[i]=a[1]-b[n];
            }else{
                c[i]=a[i]-b[i-1];
            }
            if(c[i]>0) sum+=c[i];  //补枪数 
        }
        
        for(i=1;i<=n;i++){
            if(c[i]>0){
                minn=min(minn,sum-c[i]+a[i]); 
            }else{
                minn=min(minn,sum+a[i]);
            }
        }
        cout<<minn<<endl;
    }
     return 0;
}
View Code

E - Kind Anton

题意：给数组a,b;数组a中的元素只能包含0，1，-1，a中的元素可以通过aj=aj+ai(1<=i<j<=n)改变，判断是否能将数组a变成数组b

题解：如果a[i]<b[i] 就要使a[i]变大，判断a[i]前面有没有1,如果a[i]>b[i],就要使a[i]变小，判断a[i]前面有没有-1

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int a[100005],b[100005];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,flag=1,counts1=0,counts2=0;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        for(int i=0;i<n;i++){
            cin>>b[i];
        }
        for(int i=0;i<n;i++){
            
            if(b[i]>a[i]&&counts1==0){
                flag=0;
                break;
            }else if(b[i]<a[i]&&counts2==0){
                flag=0;
                break;
            }
            if(a[i]==1){
                counts1++;
            }
            if(a[i]==-1){
                counts2++;
            }
        }
        if(flag){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
        return 0;
}
View Code

 

推荐阅读