第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-664 接水问题

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-664 接水问题

前言

关于数学的疑问

算法训练接水问题

C语言

C 语言

Java语言

Python语言

总结

第六届——第十三届省赛题解

第六届——第十二届国赛题解

前言

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

关于数学的疑问

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

1、简单数学(基础运算) 2、位运算 3、线性代数 4、离散数学(组合数学) 5、初等数论(整数的性质) 6、概率论 7、几何

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

算法训练接水问题

资源限制

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

问题描述

　　学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1 到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j 完成其接水量要求wj 后，下一名排队等候接水的同学k 马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j 同学第x 秒结束时完成接水，则k 同学第x 1 秒立刻开始接水。若当前接水人数n’不足m，则只有n’个龙头供水，其它m−n’个龙头关闭。现在给出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。

输入格式

　　第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。第2 行n 个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi 表示i 号同学的接水量。

输出格式

　　输出只有一行，1 个整数，表示接水所需的总时间。

样例输入

Sample Input1: 5 3 4 4 1 2 1 Sample Input2: 8 4 23 71 87 32 70 93 80 76

样例输出

Sample Output1: 4 Sample Output2: 163

输入输出样例 1 说明

　　第1 秒，3 人接水。第1 秒结束时，1、2、3 号同学每人的已接水量为1，3 号同学接完　　水，4 号同学接替3 号同学开始接水。　　第2 秒，3 人接水。第2 秒结束时，1、2 号同学每人的已接水量为2，4 号同学的已接　　水量为1。　　第3 秒，3 人接水。第3 秒结束时，1、2 号同学每人的已接水量为3，4 号同学的已接　　水量为2。4 号同学接完水，5 号同学接替4 号同学开始接水。　　第4 秒，3 人接水。第4 秒结束时，1、2 号同学每人的已接水量为4，5 号同学的已接　　水量为1。1、2、5 号同学接完水，即所有人完成接水。　　总接水时间为4 秒。

数据规模和约定

　　1 ≤ n ≤ 10000，1 ≤m≤ 100 且m≤ n；　　1 ≤ wi ≤ 100

题解：

C语言

代码语言：javascript复制

#include <stdio.h>
int dm[101]={0};
int w[10001];
int t=1;
int bj=0;
int main()
{
	int n,m,i,j,d=1;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i  )
	scanf("%d",&w[i]);
	while(1)
	{
		for(i=1;i<=m;i  )
		{
			if(dm[i]==0)//若有水龙头 这一单位时间 没使用 则替换 接水者 
			{
				if(d<=n)dm[i]=d  ;//dm[i]  i 代表 水龙头 编号 dm[i]存储 这一单位时间 接水人编号 
			}
			if(dm[i]!=0)//水龙头有人接水  本水龙头接水人节水量-1 
			{
				w[dm[i]]-=1; if(w[dm[i]]==0)dm[i]=0;bj=1;}//这一单位本水龙头接水人接水量为0则空出水龙头
			}
			if(bj!=1)
				break; //bj==1则表示 本次单位时间 有水龙头使用 bj==0则标记本单位时间没水龙头使用则所有过程上一秒已完成   
			bj=0;
			t  ;
		}
	printf("%dn",t-1);
	return 0;
}

C 语言

代码语言：javascript复制

#include <iostream>
#include <string>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <map>
using namespace std;
int findmin(int a[],int n)
{
	int i;
	int min=*min_element(a,a n);
	for(i=0;i<n;i  )
	{
		if(min==a[i])
			return i;
	}
	return -1;
}
int main()
{   
	int n,m;
	cin>>n>>m;
	int *w,*time;
	w=new int[n 1];
	time=new int [m];
	for(int i=1;i<=n;i  )
	{
		cin>>w[i];
	}
	for(int i=0;i<m;i  )
	{
		time[i]=w[i 1];
	}
	int j=m 1;
	while(j<=n)
	{
		time[findmin(time,m)] =w[j];
		j  ;
	}
	int max=*max_element(time,time m);
	cout<<max;
	return 0;
}

Java语言

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

代码语言：javascript复制

import java.io.*;
import java.math.*;
import java.util.*;


public class Main {

    static final int INF = 0x3f3f3f3f;
    static final long LNF = 0x3f3f3f3f3f3f3f3fL;

    public static void main(String[] args) throws IOException {
        initReader();
     int n=nextInt();
     int m=nextInt();
     int s=Math.min(n,m);
     int[]f=new int[n];
     for(int i=0;i<n;i  )f[i]=nextInt();
     Arrays.sort(f,0,s);
     for(int i=s;i<n;i  ){
         f[0]=f[0] f[i];
         Arrays.sort(f,0,s);
     }
     pw.println(f[s-1]);
        pw.close();
    }

    static BufferedReader reader;
    static StringTokenizer tokenizer;
    static PrintWriter pw;

    public static void initReader() throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
        pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    }

    public static boolean hasNext() {
        try {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
        } catch (Exception e) {
            return false;
        }
        return true;
    }

    public static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    public static String nextLine() {
        try {
            return reader.readLine();
        } catch (Exception e) {
            return null;
        }
    }

    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    public static char nextChar() throws IOException {
        return next().charAt(0);
    }
}

Python语言

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

代码语言：javascript复制

n,m = input().split()
s = list(map(int,input().split()[:int(n)]))
a = s[:int(m)]
for i in s[int(m):]:
    a[a.index(min(a))]  = i
print(max(a))

总结

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

第六届——第十三届省赛题解

所有的题目都做了讲解，最难的有配套的视频，视频提供者是【2020级的弓家宜】先生。

第六届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123284163
第七届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123285783
第八届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123302677
第九届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123303285
第十届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123319090
第十一届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123320205
第十二届Java省赛C组第一套	https://laoshifu.blog.csdn.net/article/details/123413141
第十二届Java省赛C组第二套	https://laoshifu.blog.csdn.net/article/details/123413271
第十三届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/128891276

第六届——第十二届国赛题解

所有题目均有题解，部分第10题非最优解，至少跑20%数据。

第六届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123440705
第七届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123442982
第八届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123443626
第九届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123443908
第十届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123444946
第十一届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123445601
第十二届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123446589

java https 网络安全 c语言 python

0 人点赞

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-664 接水问题