首页 > 试题广场 >

年会抢玩偶游戏

[编程题]年会抢玩偶游戏
  • 热度指数:3426 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

某公司年会上,组织人员安排了一个小游戏来调节气氛。游戏规则如下:

N个人参与游戏,站成一排来抢工作人抛来的M个小玩偶。为了增加游戏的趣味和难度,规则规定,参与游戏的人抢到的礼物不能比左右两边的人多两个或以上,否则会受到一定的惩罚。游戏结束时拥有玩偶最多的人将获得一份大奖。
假设大家都想赢得这份大奖,请问站在第K个位置的小招在赢得游戏时,最多能拥有几个玩偶?

输入描述:
输入为用空格分隔的3个正整数,依次为:参与游戏人数N、玩偶数M、小招所在位置K


输出描述:
输出为1个正整数,代表小招最多能够拥有的玩偶数。若没有,则输出0。
示例1

输入

1 1 0

输出

0
示例2

输入

1 3 1

输出

3
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();
            // 特殊情况
            if(n==0 || m==0 || k<=0 || k>n) {
                System.out.println(0);
            } else {
                // 参与游戏的人抢到的礼物不能比左右两边的人多两个或以上
                // 即小招左右两边的人最少分别为小招的玩偶数减一,即max-1
                // 为了让小招玩偶数尽量多,离校招越远的人玩偶数越少,呈依次减一的情形
                for (int max = m; max >0; max--) {
                    int sum = max;
                    for (int i = 1; i <= k-1; i++) {
                        sum += (max-i)>0?(max-i):0;
                    }
                    for (int i = 1; i <= n-k; i++) {
                        sum += (max-i)>0?(max-i):0;
                    }
                    if(sum<=m) {
                        System.out.println(max);
                        break;
                    }
                }
            }
        }
    }
}
发表于 2018-08-13 19:40:20 回复(3)
# 考虑每次K位置加1时,要给左右两边加多少
# 注意边界条件
N, M, K = [int(num) for num in input().split()]
if K < 1 or K > N:
    print(0)
    exit()
if N == 1:
    print(M)
    exit()
cnt = 0
i = j = K
need = j - i + 1
while M >= need:
    cnt += 1
    M -= need
    i = max(1, i-1)
    j = min(N, j+1)
    need = j - i + 1
print(cnt)

编辑于 2019-04-03 09:01:58 回复(0)
初步想了下,逻辑对吗?
 public int test(intN, int M, int K){
    if(K==0) return 0;
    if(K==1||K==N){
         if(M%2==0) return M/2;
         else return M/2+1;
     }
     if(M%2==0) return M/2;
     else return M/2+1;
     }
}

编辑于 2018-08-12 10:07:32 回复(2)
#include <iostream>
#include <vector>

int main() {
    int num, left = 0, right = 0;
    std::vector<int> nums;
    while(std::cin >> num) {
        nums.emplace_back(num);
    }
    int p = nums[0], t = nums[1], x = nums[2];
    if(x == 0 || p == 0 || t == 0 || x > p) {
        std::cout<<0<<std::endl;
        return 0;
    }
    for(int i = 1; i < x; ++i) {
        left += i;
    }
    for(int j = 1; j <= p - x; ++j) {
        right += j;
    }
    int n = (t + left + right) / p;
    std::cout<<n<<std::endl;

    return 0;
}

发表于 2019-07-14 19:51:59 回复(1)
//自己在k位置最多,左右两边都是k-1咯,左右两边往左依次减一,往右依次减一
//建立方程,解出来就行了,ac了,不知道思想可有问题
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            int n=scan.nextInt();
            int m=scan.nextInt();
            int k=scan.nextInt();
            System.out.println(get(n,m,k));
        }
    }
    public static int get(int n,int m,int k){
        int ans=0;
        if(m==0||n==0||k<=0||k>n)
            return 0;
        else if(n==1)
            ans=m;
        else{
            k=k-1;
           ans=(m+k*k+n*n/2+k-n*k-n/2)/n;
        }
        return ans;
    }
}

发表于 2019-05-24 20:22:51 回复(1)
intn,m,k;
    scanf("%d%d%d",&n,&m,&k);
    if(k<1 || k>n){
        printf("0\n");
    }else{
        inth=0;
        for(inti=1;i<=k-1;i++){
            h+=i;
        }
         for(inti=1;i<=n-k;i++){
            h+=i;
        }
        printf("%d",(int)((m+h)/n));
    }
发表于 2018-08-16 20:07:29 回复(2)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    if(n==0 || m==0 || k<1 || k>n)
        printf("0\n");
    else{
        for(int M=m;M>0;M--){
            int s = M;
            for(int i=1;i<=k-1;i++)
                s += max(M-i, 0);
            for(int i=1;i<=n-k;i++)
                s += max(M-i, 0);
            if(s <= m){
                printf("%d\n", M);
                break;
            }
        }
    }
    return 0;
}

发表于 2020-10-22 01:21:47 回复(0)
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        int n,m,k;
        n=m=k=0;
        n=sr.nextInt();
        m=sr.nextInt();
        k=sr.nextInt();
        if(k<=0||k>n) {//超出队列
            System.out.println(0);
            return;
        }
        int[] nt=new int[n];
        int left=k-1;
        int right=n-k;
        if(left+right==0) {//左右都没人
            System.out.println(m);
            return;
        }
        if(m<=Math.min(left,right)) {//礼物少于可拿的数
            System.out.println(m);
            //return;
        }else {//最多可拿的数
            System.out.println(Math.min(left,right)+1);
        }
    }
}

发表于 2020-06-21 12:43:56 回复(0)
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner read=new Scanner(System.in);
        int N=read.nextInt(),M=read.nextInt(),K=read.nextInt(); read.close();
        if(K<1||K>N) {
            System.out.println(0);
            return ;
        }
        int[] arr=new int[N+1];
        while(M-->0) {      
            arr[K]++;  //先富
            int k=K;
            while(k+1<=N&&arr[k+1]+1<arr[k]) {  //贫富差距过大
                arr[k]--;  //带动后富
                arr[k+1]++;
                k++;
            }
            k=K;
            while(k-1>=1&&arr[k-1]+1<arr[k]) {  //实现共同富裕
                arr[k]--;
                arr[k-1]++;
                k--;
            }
        }
        System.out.println(arr[K]);
    }
}

发表于 2019-08-31 14:28:32 回复(0)
//贴一个cpp的吧
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    if(n==0 || m==0 || k<=0 || k>n) {
        cout<<0<<endl;
    }
    else{
        for(int max=m;max>=0;max--){
            int sum=max;
            for(int i=1;i<=k-1;i++){ //左边的人
                int x=max-i;
                sum+=x>0?x:0;
            }
            for(int i=1;i<n-k;i++){  //右边的人
                int x=max-i;
                sum+=x>0?x:0;
            }
            if(sum<=m){
                cout<<max;
                break;
            }
        }
    }
    return 0;
}

发表于 2019-04-15 19:03:51 回复(0)
他这个题没有说,每个人都必须有礼物吧。 他要小昭最多,那么只让他旁边的两个有max-1个不就行看?
发表于 2020-09-24 09:59:54 回复(0)
模拟。第一轮只给k一个,第二轮给k和左右的人各一个,第三轮给k和左右两人各一个……直到剩余数量不足以给出下一轮。
n, m, k = [int(x) for x in input().split()]
if not 1 <= k <= n:
    print(0)
else:
    l = r = k
    ans = 0
    while m >= r - l + 1:
        m -= r - l + 1
        l = l-1 if l > 1 else l
        r = r+1 if r < n else r
        ans += 1
    print(ans)


发表于 2022-10-13 15:27:52 回复(0)
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int K = scanner.nextInt();
        if (N == 0 || M == 0 || K <= 0 || K > N) {
            System.out.println(0);
            return;
        }
        for (int max = M; max > 0; max--) {
            int result = max;
            for (int i = K-1; i > 0; i--) {
                result += max+i-K;
            }
            for (int i = K+1; i <= N; i++) {
                result += max-i+K;
            }
            if (result <= M) {
                System.out.println(max);
                return;
            }
        }
    }
}
发表于 2021-09-27 20:21:20 回复(0)
/*
    设k位置获得x个,则k-1,k+1获得x-1个,k-2,k+2获得x-2个,以此类推,1位置获得x-(k-1)个,n位置获x-(n-k)个。
    对1~n位置获得的数量求和,得到n*x-[k-1+(k-1)*(k-2)/2]-[(n-k)+(n-k)*(n-k-1)/2],该式应该小于等于m,求x。
*/

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, k;
    while (cin >> n >> m >> k) {
        if (k == 0 || k > n)
            cout << 0 << endl;
        else if ((n == 1 && k == 1) || m < 2)
            cout << m << endl;
        else {
            int sum1 = k - 1 + (k - 1) * (k - 2) / 2;
            int sum2 = n - k + (n - k) * (n - k -1) / 2;
            int res = (m + sum1 + sum2) / n;
            cout << res << endl;
        } 
    }
    return 0;
}

发表于 2021-09-08 10:42:22 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();
        if(N < 1 || M < 1 || K < 1 || K > N){
            System.out.println(0);
            return;
        }
        if(N == 1){
            System.out.println(M);
            return;
        }
        int[] a = new int[N];
        a[K - 1] = 1;
        M--;
        while(M > 0){
            if(M < 3 || (M < 2 && (K == 1 || K == N))){break;}
            a[K - 1]++;
            M--;
            for(int i = K - 2, j = K; i > -1 && j < N; i--,j++){
                if(M > 1){
                    a[i]++;
                    a[j]++;
                    M -= 2;
                }else{break;}
            }
        }
        System.out.println(a[K - 1]);
    }
}

发表于 2021-04-07 17:51:46 回复(0)
#include<iostream>
using namespace std;
int main(){
    int n=0,m=0,k=0;
    cin >> n >> m >> k;
    if(k==0 || n==0 || m==0 || k>n)
        cout << 0;
    else
        cout << ((k-1)*(k-1) + n-1 + (k-n)*(k-n) + 2*m)/(2*n);
    return 0;
}

发表于 2021-02-19 10:13:56 回复(0)
import java.util.Scanner;
public class Main{
    public static void main(String[] argvs){
         Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int K = in.nextInt();
        
        if(N==0||M==0||K<=0||K>N)
            System.out.println(0);
        else if(N==1)
            System.out.println(M);
        else{
            int rounds = 1,sum=1,nextdis = 3;
            while(sum + nextdis<M){
                sum += (2*rounds-1);
                rounds++;
                if(rounds*2+1<=N){
                    nextdis = rounds*2+1;
                }
                else
                    nextdis += N;
            }
            System.out.println(rounds);
        }
    }
    
}
发表于 2020-08-24 16:22:36 回复(0)
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int N = in.nextInt();
            int M = in.nextInt();
            int K = in.nextInt();
            System.out.println(getMax(N,M,K));
        }
    }
    public static int getMax(int N,int M,int K){
        if(N<=0 || M<=0 || K<=0 ||K>N) return 0;
        int sum =0 ;
        int max = 0;
        if(N==2 && M==2) return 1;
        while(sum<M){
            max+=1;
            sum = (max-K+1+max)*K/2+(max+max-(N-K+1)+1)*(N-K+1)/2-max;
            if(sum==M){return max;}
            
        }
        return max-1;
        
        
    }
}
通过了所有测试用例。思路:k位置最大值是max,求所有人玩偶数量的和,k位置想要最大其他人只能是1的等差数列,sum必须不大于M。找出符合条件的max值。
发表于 2020-06-28 10:31:06 回复(1)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        if(m==0 || n==0 || kn){
            System.out.println(0);
            return;
        }
        System.out.println((m + (k*(k-1)/2) + ((n-k+1)*(n-k)/2))/n);
    }
}
发表于 2020-06-18 11:18:30 回复(0)
N,M,K = map(int,input().split(' '))
if K == 0:
    print("0")
elif K>N:
    print("0")
elif N == 1
    print(M)
else:
    num = 1
    M = M-1
    #只能比隔壁多一个
    while(K-num>0 and K+num>0 and M-num*2-1>=0):
        M = M-num*2-1
        num = num+1
    print(num)
    
发表于 2020-06-11 15:19:10 回复(0)