首页 > 其他 > 详细

2020.5.27--习题三

时间:2020-05-29 20:54:39      阅读:41      评论:0      收藏:0      [点我收藏+]

A - Sorted Adjacent Differences

 题解:给出长度为n的数组,要求重新排列使
|a1a2||a2a3||an1an|成立。。。。。方法:现将数组从大到小排列,若n为偶数,则从中间开始向两边数依次放到前面排列为新的数组,若为奇数,则最中间的数为第一个,再依次向两边放到前面

如 -2 4 5 5 6 8 --> 5 5 4 6 -2 8

1 3 5 7 9  >>  5 3 7 1 9

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int s[n+5],i,j,b[n+5];
        for(i=0;i<n;i++)cin>>s[i];
        sort(s,s+n);
        int p=0;
        if(n%2==0)
        {
            i=n/2-1;
            int h=i;
            for(i=n/2-1;i>=0;i--)
            {
                b[p++]=s[i];
                for(j=h+1;j<h+2;j++){
                    b[p++]=s[j];

                }
                h++;
            }
             for(i=0;i<n;i++)cout<<b[i]<<" ";
             cout<<endl;
        }
        else
        {
            b[p++]=s[n/2];
            int w=n/2+1;
            for(i=n/2-1;i>=0;i--)
            {
                b[p++]=s[i];
                for(j=w;j<w+1;j++)
                {
                   b[p++]=s[j];
                }
                w++;
            }
           for(i=0;i<n;i++)cout<<b[i]<<" ";
           cout<<endl;
        }
    }
}

 

B - Powered Addition

 题意:给出一组数,使该数组变为递增序列,在第x秒可以选择其中的一个或几个数增加2^(x-1),求使用的最少秒数

因为每秒都可以使任意数增加,所以直接找到递减的最大的值,计算出2的多少倍,求出x

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,i,j;
        cin>>n;
        int s[n+5];
        for(i=0;i<n;i++)cin>>s[i];
        int m=0,p=s[0],k=0;
        for(i=1;i<n;i++)
        {
            if(m<p-s[i])
            {
                k=1;
                m=p-s[i];
            }
            //cout<<m<<endl;
            if(p<s[i])p=s[i];
        }
        int ct=0;
        if(k==0)cout<<"0"<<endl;
        else
        {
            while(m)
            {
                ct++;
                m/=2;
            }
            cout<<ct<<endl;
        }
    }
}

C - Middle Class

 题意:给出一组数,从中任意选出几个数,求平均值,若达到标准数值则为有钱人,求最大数量的有钱人数

现将数组从大到小排序,每个数减去标准值,将差值加到下一个数上,差值大于等于0则满足要求

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long n,x;
        cin>>n>>x;
        long long s[n+5],i,j;
        for(i=0;i<n;i++)cin>>s[i];
        sort(s,s+n,greater<int>());
        long long ct=0,p,k=0;
        for(i=1;i<n;i++)
        {
            p=s[i-1];
           if(p>=x)
           {
               ct++;
               k=p-x;
               s[i]+=k;
               //cout<<ct<<" "<<k<<" "<<s[i]<<endl;
           }

        }
        if(s[n-1]>=x)ct++;
        cout<<ct<<endl;
    }
}

D - Circle of Monsters

 题意:n个怪物围成一个圈,每个怪物血量为ai爆炸伤害为bi,怪物被杀死后对下一个怪物造成爆炸伤害,每发子弹对怪物造成1点伤害,求杀死怪物的最少子弹数

要尽可能利用爆炸伤害,选取一个起始点 。取一个爆炸伤害对自己炸的血量最少的怪物为起点,这样其余所有爆炸伤害都可以打出来。sum()sum()+()
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=300009;
ll t,n,a[maxn],b[maxn],c[maxn],explore,sumn,minn=1e18;
int main()
{
    cin>>t;
    while(t--)
    {
        minn=1e18,sumn=0,explore=0;
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&a[i],&b[i]);
            sumn+=a[i];
        }
        for(int i=1;i<=n-1;i++)
        {
            c[i]=min(b[i],a[i+1]),explore+=c[i];
            minn=min(minn,c[i]);
        }
        c[n]=min(b[n],a[1]);
        minn=min(minn,c[n]);
        explore+=c[n];
        cout<<sumn-explore+minn<<endl;
    }
}

 

E - Kind Anton

 题意:给出两个数组a和b,数组a由1 0 -1 组成,使数组a中任意数加上该数前面的数,多次操作后数组a等于数组b则输出YES 否则输出NO

先看a中与数组b不同的数的下标前是否存在1 或-1,并记录下来就行

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        long long s[n+5],b[n+5],w[n+5]={0},a[n+5]={0},i,j;
        int p=0,q=0;
        for(i=0;i<n;i++)
        {
            cin>>s[i];
            if(p==1)w[i]=1;//只要在其本身之前出现一次-1,1,后面就都可以使用该处w[i]=1时,i>=2避免是本身下标
            if(q==1)a[i]=-1;
            if(s[i]==1)p=1;
            else if(s[i]==-1)q=1;

        }
        for(j=0;j<n;j++)cin>>b[j];
        int k=0;
        for(i=0;i<n;i++)
        {
            k=0;
            if(s[i]>b[i])
            {
               if(a[i]==-1)
                    k=1;
            }
            else if(s[i]<b[i])
            {
                if(w[i]==1)k=1;
            }
            if(s[i]==b[i])k=1;
            //cout<<k<<endl;
           if(k==0){
             cout<<"NO"<<endl;
             break;
           }
        }
        if(k==1)cout<<"YES"<<endl;
    }
}

 

F - Eugene and an array

 题意:如果一个数组的所有子数组,每个子数组数组元素和不为0,那么这是一个好数组,给你一个数组,计算它的子数组有多少是好数组

要解决题目所求首先就是找到和为0的子数组,这个在求一遍前缀和之后很容易看出,如果说前缀和数组中某两个位置的值相等(设这两个位置为left和right,即满足sum[left]==sum[right] ,那么区间[left+1,right]这一段的和必然为0。分析到这一步之后,我们尝试使用尺取法,定义双指针left,right 从左到右枚举答案区间的右端点right,并且移动left指针,以保证每一时刻双指针管辖的范围内不存在和为0的子数组序列,这个时候,以right为右端点对应的贡献就是right−left,我们把它累加到答案中即可。
       具体实现时可以使用一个map 来实时更新标记区间中的情况。注意一个细节,要考虑某位置的前缀和为0 的情况,这个时候相当于是和sum[0]相等,所以一开始要初始化标记sum[0] 。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
typedef long long ll;
ll n, a, sum[maxn];
map<ll, bool> mp;
ll solve(){ //尺取 
    ll ans = 0, left = 0, right = 1; //以right为答案区间的右端点,从左到右枚举 
    mp[0] = true;
    while(right <= n){
        while(mp[sum[right]]){
            mp[sum[left]] = false;
            ++left;
        }
        ans += right - left;
        mp[sum[right]] = true;
        ++right;
    }
    return ans;
}
int main(){
    ll i, j;
    ios::sync_with_stdio(false);
    cin>>n;
for(i=1;i<=n;++i){
        cin>>a;
        sum[i] = sum[i-1] + a;
    }
    cout<<solve();
    return 0;
}

 

2020.5.27--习题三

原文:https://www.cnblogs.com/mxw000120/p/12974605.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!