보너스 쟁탈 알고리즘

3429 단어
보 너 스 를 빼 앗 는 것 은 모두 가 알 고 있 지만 고정된 금액 의 보 너 스 를 보 내 면 몇 사람 이 빼 앗 고 어떤 규칙 을 만족 시 켜 야 합 니까?
  • 모든 사람 이 빼 앗 은 금액 의 합 은 보너스 금액 과 같 아서 초과 할 수도 없고 적 을 수도 없다.
  • 한 사람 이 적어도 한 푼 을 빼 앗 았 다.
  • 모든 사람 이 금액 을 빼 앗 을 확률 이 같다 는 것 을 보증 해 야 한다.

  • 다음은 두 가지 보 너 스 를 빼 앗 는 방법 을 실현 했다. 두 배 균일 치 법 과 선분 절단 법 이다.
    1, 2 배 평균치 법
    나머지 보너스 금액 은 M 이 고 나머지 인원 은 N 이 라면 다음 과 같은 공식 이 있다. = Random(0, M / N * 2).
    이 공식 은 매번 무 작위 금액 의 평균 값 이 같 고 보 너 스 를 빼 앗 는 선후 순서 로 인해 불공평 하지 않다 는 것 을 보증 했다.
    밤 을 들다
    10 명 이 있다 고 가정 하면 보너스 총액 은 100 위안 이다.
    100 / 10 * 2 = 20 이 므 로 첫 번 째 사람의 무 작위 범 위 는 (0, 20) 이 고 평균 10 원 을 뺏 을 수 있 습 니 다. 첫 번 째 사람 이 무 작위 로 10 원 이 된다 고 가정 하면 나머지 금액 은 100 - 10 = 90 원 입 니 다.
    90 / 9 * 2 = 20 이 므 로 두 번 째 사람의 무 작위 범 위 는 똑 같이 (0, 20) 이 고 평균 10 원 을 뺏 을 수 있 습 니 다. 두 번 째 사람 이 무 작위 로 10 원 이 라 고 가정 하면 나머지 금액 은 90 - 10 = 80 원 입 니 다.
    80 / 8X2 = 20 이기 때문에 세 번 째 사람의 무 작위 범 위 는 똑 같이 (0, 20) 이 고 평균 10 원 을 뺏 을 수 있다.
    이런 식 으로 미 루 면 마지막 을 제외 하고 매번 무 작위 범위 의 평균 값 은 같다.
    List divideRedPackage(int totalAmount, int totalPeopleNum) {
            List results = new ArrayList<>(totalPeopleNum);
            int restAmount = totalAmount;
            int restPeopleNum = totalPeopleNum;
            Random random = new Random();
            for (int i = 0; i < totalPeopleNum - 1; i++) {
                int amount = random.nextInt(restAmount / restPeopleNum * 2 - 1) + 1;
                restAmount -= amount;
                restPeopleNum--;
                results.add(amount);
            }
            results.add(restAmount);
            return results;
    }
    

    2. 선분 절단 법
    선분 절단 법 이란 무엇 입 니까? 우 리 는 보너스 총 금액 을 아주 긴 선분 으로 상상 할 수 있 습 니 다. 그리고 모든 사람 이 빼 앗 은 금액 은 이 메 인 구간 에서 분 리 된 몇 개의 서브 선분 입 니 다.
    각 자선의 길 이 를 어떻게 정 합 니까? '절단 점' 으로 정 합 니 다. N 명 이 함께 보 너 스 를 뺏 을 때 N - 1 절단 점 을 정 해 야 합 니 다. 따라서 N - 1 무 작위 연산 을 통 해 N - 1 절단 점 을 정 해 야 합 니 다. 무 작위 범위 구간 은 (1, M) 입 니 다.
    모든 절단 점 이 확정 되면 서브 라인 의 길이 도 이에 따라 확정 된다. 그러면 모든 사람 이 보 너 스 를 빼 앗 으 러 올 때 서브 라인 의 길이 와 같은 가격 의 보 너 스 를 순서대로 받 으 면 된다.
    이것 이 바로 선분 절단 법의 사고방식 이다. 여기 서 다음 과 같은 두 가 지 를 주의해 야 한다.
  • 무 작위 절단 점 이 중복 되면 어떻게 처리 합 니까?
  • 어떻게 가능 한 한 시간 복잡 도와 공간 복잡 도 를 낮 출 수 있 습 니까?
  • List lineCut(int money, int people) {
    
            if (money < 1 || people < 1 || money < people) return;
    
            List team = new ArrayList<>(people - 1);
            List result = new ArrayList<>(people);
    
            Random random = new Random();
            while (team.size() < people - 1) {
                int randomMoney = random.nextInt(money) + 1;
                if (!team.contains(randomMoney)) {
                    team.add(randomMoney);
                }
            }
    
            Collections.sort(team);
    
            System.out.print("   :");
            System.out.println(team);
    
            int left = 0;
            for (int i = 0; i < team.size(); i++) {
                result.add(team.get(i) - left);
                left = team.get(i);
            }
            result.add(money - left);
    
            System.out.print("    :");
            System.out.println(result);
    
            //                 
            Optional r = result.stream().reduce(Integer::sum);
            System.out.print("   :");
            System.out.println(r.get());
            return result;
    }
    

    《 만화: 어떻게 보너스 쟁탈 알고리즘 을 실현 합 니까? 》 를 참고 하 세 요.

    좋은 웹페이지 즐겨찾기