2020-05-26 — 习题训练三

A - Sorted Adjacent Differences

题意，重新排列使序列符合规定

思路，先排序，从两头向中间依次输出即可

代码：

/*
  \\               //
   \\             //
    \\           //
##DDDDDDDDDDDDDDDDDDDDDD##
## DDDDDDDDDDDDDDDDDDDD ##
## hh   /\     ***** hh ##
## hh  //\\   **     hh ##
## hh //__\\  **     hh ##
## hh//    \\  ***** hh ##
## hh      wwww      hh ##
## hh                hh ##
## MMMMMMMMMMMMMMMMMMMM ##
##MMMMMMMMMMMMMMMMMMMMMM##
     \/            \/
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<math.h>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fora(i,a,b) for (int i = (a); i < (b); i++)
#define fors(i,a,b,s) for (int i = (a); i < (b); i=i+(s))
int a[100005],b[100005];
// 你好，我叫赵师哥 
int main(){
	int n,t,m;
	cin>>t;
	while(t--){
		cin>>n;
		memset(b,0,sizeof(b));
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		int ans=0;
		sort(a,a+n);
		for(int i=0,j=n-1;i<j;i++,j--){
			b[ans]=a[i];
			ans++;
			b[ans]=a[j];
			ans++;
		}
		if(n%2){
			b[ans]=a[n/2];	//憨批这里从0开始！！！！ 
		}
		for(int i=n-1;i>=0;i--){
			cout<<b[i]<<" ";
		}
		cout<<endl; 
	}
	return 0;
}

B - Powered Addition

题意：给你一个数组，你可以在第x秒选一些元素让它们都加上 2^（x-1），问至少需要多少秒可以使数组变成非递减的数组。

思路：此题采用贪心算法，找出相差最大的值，然后判断是2的多少倍即可、

代码：

/*
  \\               //
   \\             //
    \\           //
##DDDDDDDDDDDDDDDDDDDDDD##
## DDDDDDDDDDDDDDDDDDDD ##
## hh   /\     ***** hh ##
## hh  //\\   **     hh ##
## hh //__\\  **     hh ##
## hh//    \\  ***** hh ##
## hh      wwww      hh ##
## hh                hh ##
## MMMMMMMMMMMMMMMMMMMM ##
##MMMMMMMMMMMMMMMMMMMMMM##
     \/            \/
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<math.h>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fora(i,a,b) for (int i = (a); i < (b); i++)
#define fors(i,a,b,s) for (int i = (a); i < (b); i=i+(s))
// 你好，我叫赵师哥 
ll a[100005];
ll sum[50];
int main()
{
    sum[0]=1;
    for(ll j=1;j<=40;j++)
    {
        sum[j]=(1LL<<j)+sum[j-1];
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll maxx=0-1e10;
        ll ans=0;
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&a[i]);
            maxx=max(maxx,a[i]);
            if(a[i]<maxx)
            {
                for(ll j=0; j<=40; j++)
                {
                    //cout<<((1LL)<<j)+a[i]<<endl;
                    if(sum[j]+a[i]>=maxx)
                    {
                        ans=max(ans,j+1);
                        break;
                    }
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

C - Middle Class

题意：给一个序列可以平均算，求能大于某个数最大的个数是多少

思路：先排序，从大到小依次循环，如果大于要求值就把多余的提取出来加到一起，如果小于，就从和里借，直到和小于0

代码：

/*
  \\               //
   \\             //
    \\           //
##DDDDDDDDDDDDDDDDDDDDDD##
## DDDDDDDDDDDDDDDDDDDD ##
## hh   /\     ***** hh ##
## hh  //\\   **     hh ##
## hh //__\\  **     hh ##
## hh//    \\  ***** hh ##
## hh      wwww      hh ##
## hh                hh ##
## MMMMMMMMMMMMMMMMMMMM ##
##MMMMMMMMMMMMMMMMMMMMMM##
     \/            \/
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<math.h>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fora(i,a,b) for (int i = (a); i < (b); i++)
#define fors(i,a,b,s) for (int i = (a); i < (b); i=i+(s))
// 你好，我叫赵师哥 
int a[100005];
int main(){
	int n,m,t,x;
	cin>>t;
	while(t--){
		cin>>n>>x;
		fora(i,0,n){
			cin>>a[i];
		}
		int l=n,r;
		long long sum=0;
		int ans=0;
		sort(a,a+n);
		for(int i=n-1;i>=0;i--){
			if(a[i]-x>=0){
				sum+=(a[i]-x);
				ans++;
			}
			else{
				break;
			}
		}
		if(ans==0){
			cout<<0<<endl;
			continue;
		}
		for(int i=n-ans;i>=0;i--){
			if(x-a[i]>0){
				if(sum>=x-a[i]){
				sum-=(x-a[i]);
				ans++;
			}
			else
				break;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

D - Circle of Monsters

题意：怪兽围成一个圈，血量小于等于0时死亡，并会炸到下一怪兽，求最小使用多少次技能把怪兽杀干净

思路：首先发现打死某一头怪兽有两种方法：1.直接打死 2.先打死前面一头，把怪兽炸残（或者直接炸死）再打死。可以关注到显然第二种会更优，但是肯定要选择一头怪兽用第一种方案打死，再不断推进用第二种方式打死全部怪兽，所以我们设c_i表示第 i 头怪兽被炸之后还剩的血量，有 c_i = max (0, a_i - b_i-1),特别的 c_1=\max(0, a_1-b_n)，然后枚举那个唯一的使用第一种方案打死的怪兽，找到最小的方案就行。

代码：

/*
  \\               //
   \\             //
    \\           //
##DDDDDDDDDDDDDDDDDDDDDD##
## DDDDDDDDDDDDDDDDDDDD ##
## hh   /\     ***** hh ##
## hh  //\\   **     hh ##
## hh //__\\  **     hh ##
## hh//    \\  ***** hh ##
## hh      wwww      hh ##
## hh                hh ##
## MMMMMMMMMMMMMMMMMMMM ##
##MMMMMMMMMMMMMMMMMMMMMM##
     \/            \/
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<math.h>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fora(i,a,b) for (int i = (a); i < (b); i++)
#define fors(i,a,b,s) for (int i = (a); i < (b); i=i+(s))
// 你好，我叫赵师哥 
ll a[300001], b[300001], c[300001];
int main (){
    int T;
    scanf("%d", &T);
    while(T--){
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
                scanf("%lld%lld", &a[i], &b[i]);
        for (int i = 2; i <= n; i++)
                c[i] = max(0ll, a[i] - b[i - 1]);
        c[1] = max(0ll, a[1] - b[n]);
        ll sum = 0, Min = 9e18;
        for (int i = 1; i <= n; i++)
                sum += c[i];
        for (int i = 1; i <= n; i++)
                Min = min(Min, sum - c[i] + a[i]);
        printf("%lld\n", Min);
    }
    return 0;
}

E - Kind Anton

题意：给出两个序列，问能不能第一个序列经过按照前面的数可以加到后面的数的规则处理后变成第二个序列

思路：我们从后往前枚举，每次判断 a_i与 b_i的大小。如果比 b_i小就判断前面有没有1，比 b_i大就判断有没有?1。没有直接输出 NO。最后如果全部都能遍历就代表答案为 YES。

代码：

/*
  \\               //
   \\             //
    \\           //
##DDDDDDDDDDDDDDDDDDDDDD##
## DDDDDDDDDDDDDDDDDDDD ##
## hh   /\     ***** hh ##
## hh  //\\   **     hh ##
## hh //__\\  **     hh ##
## hh//    \\  ***** hh ##
## hh      wwww      hh ##
## hh                hh ##
## MMMMMMMMMMMMMMMMMMMM ##
##MMMMMMMMMMMMMMMMMMMMMM##
     \/            \/
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<math.h>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fora(i,a,b) for (int i = (a); i < (b); i++)
#define fors(i,a,b,s) for (int i = (a); i < (b); i=i+(s))
// 你好，我叫赵师哥 
int t, n, a[100010], b[100010], cnt[2];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d",a+i);
			if(i<n){
				if(a[i]==1)
					cnt[1]++;
				if(a[i]==-1)
					cnt[0]++;
			}
		}
		for(int i=1;i<=n;++i)
			scanf("%d",b+i);
		bool flag=1;
		for(int i=n; i>=1;--i){
			if(a[i]==b[i]){
				if(a[i-1]==1)
					cnt[1]--;
				if(a[i - 1] == -1)
					cnt[0]--;
			}
			if(a[i] > b[i]){
				if(!cnt[0]){
					flag = 0;
					break;
				}
				if(a[i-1]==1)
					cnt[1]--;
				if(a[i-1]==-1)
					cnt[0]--;
			}
			else if(a[i]<b[i]){
				if(!cnt[1]){
					flag=0;
					break;
				}
				if(a[i-1]==1)
					cnt[1]--;
				if(a[i-1]==-1)
					cnt[0]--;
			}
		}
		if(!flag)
			puts("NO");
		else
			puts("YES"); 
		memset(cnt,0,sizeof(cnt));
	}
	return 0;
} 

F - Eugene and an array

看了题解，发现自己还是不会

2020-05-26 — 习题训练三

原文：https://www.cnblogs.com/pioneerjiesen/p/12989566.html