排队打水(Java)
JAVA 排队
2023-09-14 09:14:24 时间
排队打水
有 n 个人排队到 1 个水龙头处打水,第 i 个人装满水桶所需的时间是 ti,请问如何安排他们的打水顺序才能使所有人的等待时间之和最小?
输入格式
第一行包含整数 n。
第二行包含 n 个整数,其中第 i 个整数表示第 i 个人装满水桶所花费的时间 ti。
输出格式
输出一个整数,表示最小的等待时间之和。
数据范围
1≤n≤105,
1≤ti≤104
输入样例:
7
3 6 1 4 2 5 7
输出样例:
56
提交代码
import java.util.*;
public class Main
{
static int N = 100010;
static int [] t = new int [N];
public static void main(String[] args)
{
Scanner in = new Scanner (System.in);
int n = in.nextInt();
for (int i = 0; i < n; ++ i) t[i] = in.nextInt();
Arrays.sort (t, 0, n);
long ans = 0;
for (int i = 0; i < n; ++ i) ans += t[i] * (n - i - 1);
System.out.println(ans);
}
}
每天一道算法题
最长连续不重复子序列
给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数(均在 0∼105 范围内),表示整数序列。
输出格式
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
输入样例:
5
1 2 2 3 5
输出样例:
3
提交代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], s[N];
int n, res;
int main()
{
cin >> n;
for (int i = 0; i < n; ++ i) cin >> a[i];
for (int i = 0, j = 0; i < n; ++ i)
{
s[a[i]] ++; // 记录下a[i]出现的次数
while(s[a[i]] > 1) // 一点碰见两个重复的元素后
{
s[a[j]] --; // 这里要主要的一点是这个算法是没有回溯的
// 不要被for循环里面的条件误导以为会回溯、
// 现在遇到两个相同的元素了
// !!! 现在是这个算法最厉害的地方
// 这个j代表的是 j可以到达最左的地方 所以在j左边的
// 元素的个数就需要都-- 这点很妙
// 每次求的是 j到i之间的符合条件的最大值
j ++; // 然后j++
}
res = max(res, i - j + 1); // 这个res的含义是 在i这个位置、
// 可以达到的符合题目条件的最大长度
}
cout << res;
return 0;
}
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws IOException{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int [] a = new int [n + 10];
int [] s = new int [n + 10];
int res = 0;
for (int i = 0; i < n; ++ i) a[i] = in.nextInt();
for (int i = 0, j = 0; i < n; ++ i)
{
s[a[i]] ++;
while(s[a[i]] > 1)
{
s[a[j]] --;
j ++;
}
res = Math.max(res, i - j + 1);
}
System.out.println(res);
}
}
合并集合
一共有 n 个数,编号是 1∼n,最开始每个数各自在一个集合中。
现在要进行 m 个操作,操作共有两种:
M a b,将编号为 a 和 b 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
Q a b,询问编号为 a 和 b 的两个数是否在同一个集合中;
输入格式
第一行输入整数 n 和 m。
接下来 m 行,每行包含一个操作指令,指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b,都要输出一个结果,如果 a 和 b 在同一集合内,则输出 Yes,否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤105
输入样例:
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例:
Yes
No
Yes
提交代码
#include<iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[N];
int find(int x) // 找到x的祖先节点
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) p[i] = i;
while (m--)
{
char op;
int a, b;
scanf (" %c%d%d", &op, &a, &b);
if (op == 'M') p[p[find(a)]] = find(b); // 让a的祖先节点指向b的祖先节点
else
{
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
import java.io.*;
public class Main
{
static int N = 100010;
static int n, m;
static int [] p = new int [N];
static int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader (System.in));
String [] str = reader.readLine().split(" ");
n = Integer.parseInt(str[0]);
m = Integer.parseInt(str[1]);
for (int i = 1; i <= n; ++ i) p[i] = i;
while (m -- > 0)
{
String op;
int a, b;
str = reader.readLine().split(" ");
op = str[0];
a = Integer.parseInt(str[1]);
b = Integer.parseInt(str[2]);
if (op.equals("M")) p[find(a)] = find(b);
else
{
if (find(a) == find(b)) System.out.println("Yes");
else System.out.println("No");
}
}
}
}
相关文章
- java基础知识回顾之java Thread类学习(四)--java多线程安全问题(锁)
- JAVA学习(三):Java基础语法(变量、常量、数据类型、运算符与数据类型转换)
- Java实现 LeetCode 748 最短完整词(字母拆分+暴力)
- Java实现 LeetCode 556 下一个更大元素 III(数组的翻转)
- Java实现 LeetCode 107 二叉树的层次遍历 II(二)
- java实现第三届蓝桥杯地址格式转换
- java实现第四届蓝桥杯金蝉素数
- Java实现第九届蓝桥杯全球变暖
- Java 实现 蓝桥杯 历届试题 分糖果
- Java实现 蓝桥杯VIP 算法提高 插入排序
- Java实现 蓝桥杯VIP 算法提高 排队打水问题
- Java 蓝桥杯 算法训练 字符串的展开 (JAVA语言实现)
- Java核心知识点学习----线程中的Semaphore学习,公共厕所排队策略
- 【JAVA】java中的length和length()
- Google Java 编程风格指南
- Atitit mysql数据库自定义异常在java里面的捕获与处理推荐标准与规范
- atitit.http get post的原理以及框架实现java php
- 华为OD机试 - 星际篮球争霸赛(Java & JS & Python)
- Java异常机制
- Java — java.lang.NullPointerException - 如何处理空指针异常
- 【Java】java 环境配置(详细教程)
- 【java】Java中-> 是什么意思?
- 详解jvm之java类加载机制和类加载器(ClassLoader) 深入理解Java类加载器(ClassLoader) 如何自定义类加载器 深入说明双亲委派 双亲委派模型的破坏者-线程上下文类加载器
- mysql-connector-java与Mysql、Java的对应版本
- 华为校招机试 - 指令排序(Java & JS & Python)
- 【java】Java 接口(Interface)
- 【java】Java 集合框架