第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-998 娜神平衡-阿里云开发者社区

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-998 娜神平衡

前言

这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。

关于数学的疑问

蓝桥杯中涉及到的数学说多不多，说少也不少，这里罗列了一下能用到的，其中红色的是【大学C组】会使用到的

1、简单数学(基础运算)

2、位运算

3、线性代数

4、离散数学(组合数学)

5、初等数论(整数的性质)

6、概率论

7、几何

虽然看到了线性代数、离散数学、初等数论，但是对于C组来说不会考的太复杂，会基础就好。

算法训练娜神平衡

资源限制

内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

问题描述

　　娜娜是一个特别可爱的女孩子，作为学神的她最近在情感方面出现了一点点小问题。

　　她暗恋的琦琦是一名学霸，他只喜欢长得漂亮和学习很好的女生。

　　娜娜学习确实很神，但是她在琦琦面前却总是表现不出平时的神力。

　　琦琦感受到了娜娜对他的爱，但是他还是觉得娜娜的学习并不是特别好，于是他出了一道题给娜娜。

　　“娜娜，我们之间的关系需要在不断深入的同时保持一定的平衡，不可以你总是强势或者我总是弱势。”

　　琦琦给了娜娜一些两两不等的数，希望娜娜能把这些数分成两组A和B，满足以下条件：

　　1：每一次只能操作一个数，即只取出一个数分入A中或B中；

　　2：每一次操作完成后，A中数之和与B中数之和的差不能超过r。

　　新时代的丘比特们啊，帮帮娜娜吧！

输入格式

　　输入共两行。

　　第一行包括两个正整数n和r，n表示琦琦一共给了n个数，r的意义见题目描述。

　　第二行包括n个正整数，分别表示琦琦给的n个数。

输出格式

　　输出共两行，分别把A与B两组数按从小到大输出。

　　注意输入中n个数的第一个必须分入A组。

　　琦琦保证这样的输出唯一。

样例输入

4 10

9 6 4 20

样例输出

4 6 9

20

样例说明

　　先把4和6先后分入A组，再把20分入B组，最后把9分入A组。

数据规模和约定

　　很小，真的很小。

题解：

C语言

#include<stdio.h>
#include<math.h>
#include<stdbool.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
void shellSort(int *a, int len) ;
typedef long long ll;
int a[1005],val1[1005],val2[1005];
int n,r,tem,idx1,idx2;
void init(){
    memset(val1,0,sizeof(val1));
    memset(val2,0,sizeof(val2));
    idx1=idx2=0;
}
bool check(){
    int x=0,y=0,sum1=0,sum2=0,flag=1;
    sum1=val1[++x];
    while(abs(sum1-sum2)<=r&&flag){
        flag=0;
        if(abs(sum1+val1[x+1]-sum2)<=r&&x+1<=idx1){
            x++;
            flag=1;
            sum1+=val1[x];
        }
        if(abs(sum1-val2[y+1]-sum2)<=r&&y+1<=idx2){
            y++;
            flag=1;
            sum2+=val2[y];
        }
    }
    if(x==idx1&&y==idx2){
        return true;
    }
    else{
        return false;
    }
}
void print1(){
  int j;
    for( j=1;j<=idx1;j++){
            printf("%d ",val1[j]);
        }
    printf("\n");
}
void print2(){
  int j;
    for( j=1;j<=idx2;j++){
        printf("%d ",val2[j]);
    }
    printf("\n");
}
int main(){
  int i,j;
    scanf("%d%d",&n,&r);
    for( i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    tem=a[1];
    shellSort(a+1, n) ;
    for( i=0;i<(1<<n);i++){
        int judge=0;
        init();
        val1[++idx1]=a[1];
        for( j=1;j<n;j++){
            if((1<<j)&i){
                val1[++idx1]=a[j+1];
            }
            else{
                val2[++idx2]=a[j+1];
            }
        }
        if(check()){
            for( j=1;j<=idx1;j++){
                if(val1[j]==tem)
                    judge=1;
            }
            if(judge){
                print1();
                print2();
            }
            else{
                print2();
                print1();
            }
            break;
        }
    }
    return 0;
}
void shellSort(int *a, int len) {
  int i, j, k, tmp, gap;
  for (gap = len / 2; gap > 0; gap /= 2) {
    for (i = 0; i < gap; ++i) {
      for (j = i + gap; j < len; j += gap) {
        tmp = a[j];
        k = j - gap;
        while (k >= 0 && a[k] > tmp) {
          a[k + gap] = a[k];
          k -= gap;
        }
        a[k + gap] = tmp;
      }
    }
  }
}

C++语言

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void output(vector<int> &A, int as)
{
  for(int i = 0; i < as; ++i)
  {
    cout << A[i] << (i == as-1 ? '\n' : ' ');
  } 
}
void f(vector<int> &v, vector<int> &A, vector<int> &B, int a, int b, int r, int n, vector<bool> &flag, bool &mark)
{
  int as = A.size();
  int bs = B.size();
  if(n == as + bs)
  {
    mark = false;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    output(A, as);
    output(B, bs);
    return;
  }
  
  for(int i = 0; i < n; ++i)
  {
    if(flag[i])
    {
      if(abs(a + v[i] - b) <= r)
      {
        A.push_back(v[i]);
        flag[i] = false;
        f(v, A, B, a+v[i], b, r, n, flag, mark);
        flag[i] = true;
        A.pop_back();
      }
      if(!mark) break;
      
      if(i > 0 && abs(b + v[i] - a) <= r)
      {
        B.push_back(v[i]);
        flag[i] = false;
        f(v, A, B, a, b+v[i], r, n, flag, mark);
        flag[i] = true;
        B.pop_back();
      }
      if(!mark) break;
    }
  }
  
}
int main()
{
  int n = -1;
  cin >> n;
  int r = -1;
  cin >> r;
  
  vector<int> v(n);
  for(int i = 0; i < n; ++i)
  {
    cin >> v[i];
  }
  
  vector<int> A;
  vector<int> B;
  vector<bool> flag(n, true);
  bool mark = true;
  
  f(v, A, B, 0, 0, r, n, flag, mark);
  
  return 0;
}

Java语言

在扫描输入内容上会有不同的方法，但是与Scanner的用法是相同的。只是相对的录入速度快于Scanner这样在整体运算的过程中可以适当节约时间。

import java.io.*;
import java.util.*;
public class Main {
  static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
  // A B数组的下标
  static int idxa = 0, idxb = 0;
  static int[] A, B;
  static int r = 0;
  public static void main(String[] args) throws IOException {
    String[] in = reader.readLine().trim().split(" ");
    int n = Integer.parseInt(in[0]);
    r = Integer.parseInt(in[1]);
    int[] num = new int[n];
    in = reader.readLine().trim().split(" ");
    for (int i = 0; i < n; i++) {
      num[i] = Integer.parseInt(in[i]);
    }
    // 先记录下第一个数
    int first = num[0];
    Arrays.sort(num);
    // 状态搜索，n个数，用1表示在A数组中，用0表示在B数组中
    for (int i = 1; i < (1 << n) - 1; i++) {
      // 要排除全为0、全为1的情况
      idxa = 0;
      idxb = 0;
      A = new int[n];
      B = new int[n];
      for (int j = 0; j < n; j++) {
        // 当前位为1就存A
        if (((1 << j) & i) != 0) {  // 注意一定是不等于0，而不是一定等于1
          A[idxa++] = num[j];
        } else {
          B[idxb++] = num[j];
        }
      }
      // 每个数都放好位置了
      if (check()) {
        // 找存第一个数字的数组
        boolean is = false;
        for (int j = 0; j < idxa; j++) {
          if (A[j] == first) {
            is = true;
            break;
          }
        }
        if (is) {
          for (int j = 0; j < idxa; j++) {
            log.write(A[j] + " ");
          }
          log.write("\n");
          for (int j = 0; j < idxb; j++) {
            log.write(B[j] + " ");
          }
        } else {
          for (int j = 0; j < idxb; j++) {
            log.write(B[j] + " ");
          }
          log.write("\n");
          for (int j = 0; j < idxa; j++) {
            log.write(A[j] + " ");
          }
        }
        break;
      }
    }
    log.flush();
  }
  static boolean check() {
    int i = 0, j = 0, suma = 0, sumb = 0;
    // 按照题意，第一个数先放A数组
    suma += A[i++];
    boolean flag = true;
    while (Math.abs(suma - sumb) <= r) {
      flag = false;
      // 如果A中当前数可以放A，那就放A
      if (i < idxa && Math.abs(suma + A[i] - sumb) <= r) {
        suma += A[i++];
        flag = true;
      }
      // 如果B中当前数可以放B，那就放B
      if (j < idxb && Math.abs(suma - B[j] - sumb) <= r) {
        sumb += B[j++];
        flag = true;
      }
      if (flag == false) {
        break;
      }
    }
    if (i == idxa && j == idxb) return true;
    return false;
  }
}

Python语言

相对简洁，但是需要对Python的一些语法很了解，特别是列表推导式的熟悉。

import math
n, r = list(map(int, input().split()))
nums = list(map(int, input().split()))
global f1
f1 = nums[0]
nums.sort()
flag = 0
def dfs(a, b, step):
    global nums, flag
    if abs(sum(a) - sum(b)) > r and step == 1:
        pass
    elif abs(sum(a) - sum(b)) > r:
        return
    if len(nums) == 0:
        flag = 1
        a.sort()
        b.sort()
        if f1 in a:
            for i in a:
                print(i, end=' ')
            print()
            for j in b:
                print(j, end=' ')
        if f1 in b:
            for i in b:
                print(i, end=' ')
            print()
            for j in a:
                print(j, end=' ')
        return
    for i in range(len(nums)):
        a.append(nums[i])
        nums.pop(i)
        dfs(a, b, step + 1)
        if flag == 1:
            return
        nums.insert(i, a.pop())
    for i in range(len(nums)):
        b.append(nums[i])
        nums.pop(i)
        dfs(a, b, step + 1)
        if flag == 1:
            return
        nums.insert(i, b.pop())
dfs([], [], 0)

总结

没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-998 娜神平衡