【备战秋招】每日一题:4月29日美团春招第三题:题面+题目思路 + C++/python/js/Go/java带注释
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
为了更好的阅读体检为了更好的阅读体检可以查看我的算法学习博客第三题-酒王
题目内容
塔子哥和他的朋友们共 n 人是一群热爱生活的年轻人他们经常在一起吃饭聊天玩游戏。有一天他们决定去一家新开的酒吧品尝各种美酒。但是他们发现酒吧的老板是一个很奇怪的人他给他们出了一个挑战如果他们能在一个小时内喝完所有的酒就可以免单如果有人中途放弃就要付双倍的钱。塔子哥和他的朋友们觉得这是一个很有趣的游戏于是接受了挑战。
为了增加难度和乐趣他们决定用一个特殊的方式来喝酒。他们顺时针围成一圈假设标号为 1 到 n 。从 1 号开始每次从当前的人顺时针数 k 个然后这个人喝一杯酒。第 i 个人的酒量为意味着当他喝了
杯酒后将因无法忍受而离席。现在他们请你依次输出离席的人的编号以此来判断谁是酒王。
输入描述
输入第一行为两个正整数 n,k 。
输入第二行为 n 个正整数第 i 个数为 。
对于所有的数据 。
输出描述
输出一行输出用空格隔开的 n 个正整数表示按时间从早到晚离席的人的编号。
样例
输入
5 4 1 1 7 9 8
输出
1 5 2 4 3
思路
约瑟夫环问题+贪心
本题是经典的约瑟夫环问题变种。
从当前位置 cur 开始喝酒下一个位置为顺时针的 cur + k 这个位置。由于这是一个圆故一定会在一些人之间循环喝酒一部分人在这段时间总是不会喝酒我们称当前的情况为当前的酒局。喝酒的这部分人中直到存在一个人喝完酒后剩余酒杯数为 0 这一部分人的喝酒结束整个酒局将被修改。
我们需要考虑当前的喝酒的人中从当前位置 cur 开始一直顺时针 k次找下一个人而离席的第一个人必然是酒杯数最少的。
由于存在先后关系从 cur 开始顺时针 k 次找下一个喝酒的人这些人中剩余酒杯数最少且是所有剩余酒杯数最少的人中第一个喝酒的人是第一个离席的人。这个人前面的人会和他和一样多的酒后面的人会比他少喝一杯酒。
这个人离席后其顺时针后面的人就接上其位置进行下一次的酒局。
时间复杂度
类似题目推荐
LeetCode
CodeFun2000
代码
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
pair<int, int> a[N];
int ans[N], g;
int vis[N];
int people[N];
int n, k;
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; ++i) scanf("%d", &a[i].first), a[i].second = i + 1;
int cur = 0;
while (n > 0) {
for (int i = 0; i < n; ++i) vis[i] = 0;
int cnt = 0;
int minv = 0x3f3f3f3f;
// 找到当前回合所有可能需要喝酒的人
while (!vis[cur]) {
people[cnt++] = cur;
vis[cur] = 1;
minv = min(minv, a[cur].first);
cur = (cur + k) % n;
}
// 我们找到从 cur 开始的最小值
// cur 之前的人要减去 minv
// cur 之后的人要减去 minv - 1
for (int i = 0; i < cnt; ++i)
if (minv == a[people[i]].first) {
for (int j = 0; j < i; ++j) a[people[j]].first -= minv;
for (int j = i + 1; j < cnt; ++j) a[people[j]].first -= minv - 1;
// 将其排列好然后再往后走 k 个
int pos = people[i];
ans[++g] = a[pos].second;
for (int j = pos + 1; j < n; ++j) a[j - 1] = a[j];
if (n > 1) {
// 走 k - 1步是因为下一个人继承了当前离席的人的位置故从当前离席的顺时针走 k 个
cur = (pos + k - 1) % (n - 1);
}
break;
}
n -= 1;
}
for (int i = 1; i <= g; ++i) printf("%d%c", ans[i], " \n"[i == g]);
return 0;
}
python
N = 1010 n, k = map(int, input().split()) a = [[0, 0] for i in range(N)] vis = [0] * N line = input().split() for i in range(len(line)): a[i] = ([int(line[i]), i + 1]) cur = 0 ans = [] while n > 0: for i in range(n): vis[i] = 0 people = [] minv = 0x3f3f3f3f # 找到当前回合所有可能需要喝酒的人 while vis[cur] == 0: people.append(cur) vis[cur] = 1 minv = min(minv, a[cur][0]) cur = (cur + k) % n # 我们找到从 cur 开始的最小值 # cur 之前的人要减去 minv # cur 之后的人要减去 minv - 1 for i in range(len(people)): if minv == a[people[i]][0]: for j in range(i): a[people[j]][0] -= minv for j in range(i + 1, len(people)): a[people[j]][0] -= minv - 1 # 将其排列好然后再往后走 k 个 pos = people[i] ans.append(a[pos][1]) a.pop(pos) if n > 1: # 走 k - 1步是因为下一个人继承了当前离席的人的位置故从当前离席的顺时针走 k 个 cur = (pos + k - 1) % (n - 1) break n -= 1 for i in ans: print(i, end=' ') print()
Java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static final int N = 1010;
static int[] ans = new int[N], people = new int[N];
static int[] vis = new int[N];
static int[][] a = new int[N][2];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
for (int i = 0; i < n; ++i) {
a[i][0] = sc.nextInt();
a[i][1] = i + 1;
}
int g = 0;
int cur = 0;
while (n > 0) {
for (int i = 0; i < n; ++i) vis[i] = 0;
int cnt = 0;
int minv = 0x3f3f3f3f;
// 找到当前回合所有可能需要喝酒的人
while (vis[cur] == 0) {
people[cnt++] = cur;
vis[cur] = 1;
minv = Math.min(minv, a[cur][0]);
cur = (cur + k) % n;
}
// 我们找到从 cur 开始的最小值
// cur 之前的人要减去 minv
// cur 之后的人要减去 minv - 1
for (int i = 0; i < cnt; ++i) {
if (minv == a[people[i]][0]) {
for (int j = 0; j < i; ++j) {
a[people[j]][0] -= minv;
}
for (int j = i + 1; j < cnt; ++j) {
if (j != i) {
a[people[j]][0] -= minv - 1;
}
}
// 将其排列好然后再往后走 k 个
int pos = people[i];
ans[++g] = a[pos][1];
for (int j = pos + 1; j < n; ++j) {
a[j - 1] = a[j];
}
// 走 k - 1步是因为下一个人继承了当前离席的人的位置故从当前离席的顺时针走 k 个
if (n > 1) {
cur = (pos + k - 1) % (n - 1);
}
break;
}
}
n -= 1;
}
for (int i = 1; i <= g; ++i) {
System.out.print(ans[i] + " ");
}
System.out.println();
}
}
Go
package main
import "fmt"
type Pair struct {
first, second int
}
const N = 1010
var a [N]Pair
var ans [N]int
var vis [N]bool
var people [N]int
var g int
var n, k int
func main() {
fmt.Scan(&n, &k)
for i := 0; i < n; i++ {
fmt.Scan(&a[i].first)
a[i].second = i + 1
}
cur := 0
for n > 0 {
for i := 0; i < n; i++ {
vis[i] = false
}
cnt := 0
minv := 0x3f3f3f3f
// 找到当前回合所有可能需要喝酒的人
for !vis[cur] {
people[cnt] = cur
vis[cur] = true
minv = min(minv, a[cur].first)
cur = (cur + k) % n
cnt++
}
// 我们找到从 cur 开始的最小值
// cur 之前的人要减去 minv
// cur 之后的人要减去 minv - 1
for i := 0; i < cnt; i++ {
if minv == a[people[i]].first {
for j := 0; j < i; j++ {
a[people[j]].first -= minv
}
for j := i + 1; j < cnt; j++ {
a[people[j]].first -= minv - 1
}
// 将其排列好然后再往后走 k 个
pos := people[i]
ans[g+1] = a[pos].second
g++
for j := pos + 1; j < n; j++ {
a[j-1] = a[j]
}
if n > 1 {
// 走 k - 1步是因为下一个人继承了当前离席的人的位置故从当前离席的顺时针走 k 个
cur = (pos + k - 1) % (n - 1)
}
break
}
}
n--
}
for i := 1; i <= g; i++ {
if i == g {
fmt.Printf("%d\n", ans[i])
} else {
fmt.Printf("%d ", ans[i])
}
}
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
Js
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
input += data;
return;
});
process.stdin.on('end', () => {
const lines = input.trim().split('\n');
[n, k] = lines[0].split(' ').map(Number);
const a = lines[1].split(' ').map((x, i) => [Number(x), i + 1]);
const people = new Array(n);
const ans = new Array(n);
let cur = 0;
let g = 0;
while (n > 0) {
const vis = new Array(n).fill(false);
let cnt = 0;
let minv = Infinity;
// 找到当前回合所有可能需要喝酒的人
while (!vis[cur]) {
people[cnt++] = cur;
vis[cur] = true;
minv = Math.min(minv, a[cur][0]);
cur = (cur + k) % n;
}
// 我们找到从 cur 开始的最小值
// cur 之前的人要减去 minv
// cur 之后的人要减去 minv - 1
for (let i = 0; i < cnt; i++) {
const p = people[i];
if (minv === a[p][0]) {
for (let j = 0; j < i; j++) {
a[people[j]][0] -= minv;
}
for (let j = i + 1; j < cnt; j++) {
a[people[j]][0] -= minv - 1;
}
// 将其排列好然后再往后走 k 个
const pos = p;
ans[g++] = a[pos][1];
for (let j = pos + 1; j < n; j++) {
a[j - 1] = a[j];
}
if (n > 1) {
// 走 k - 1 步是因为下一个人继承了当前离席的人的位置故从当前离席的顺时针走 k 个
cur = (pos + k - 1) % (n - 1);
}
break;
}
}
n--;
}
console.log(ans.join(' '));
});