요리 순서

제목 설명
한 요리사 가 n 가지 요리 의 만족 도 를 수집 했다. 이 요리 사 는 모든 요 리 를 만 드 는 시간 이 1 단위 이다.
한 가지 요리 의 '좋아 하 는 시간' 계 수 는 이 요 리 를 요리 하 는 데 걸 린 시간 과 이 요리 의 만족 도 를 곱 하 는 것 으로 정의 된다. 즉, time [i] * satisfaction [i] 이다.
모든 요 리 를 다 만 든 '좋아 하 는 시간' 의 최대 치 는 얼마 입 니까?
너 는 임의의 순서에 따라 요리 순 서 를 배정 할 수 있 고, 어떤 요 리 를 하 는 것 을 포기 해서 더 큰 총 계 를 얻 을 수도 있다.
알고리즘 사고
임의로 정렬 할 수 있 고 일부 요 리 를 포기 할 수 있 기 때문에 요리 의 순 서 는 어 릴 때 부터 커 야 한다. 다음 과 같은 알고리즘 은 새로운 요 리 를 추가 할 때마다 낡은 요 리 를 좋아 하 는 시간 이 배가 된다. 그러면 새로운 요 리 를 추가 해서 증가 하 는 시간 은 모두 n+=i 이다. n < = 0 시 에 새로운 요 리 를 추가 하면 좋아 하 는 시간 이 더 이상 증가 하지 않 는 다.이때 최대 시간 총화 가 있다.

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        n,res=0,0
        for i in satisfaction:
            n+=i
            if n<=0:break
            res+=n
        return res

실행 시: 48 ms, 모든 Python 3 제출 에서 89.76% 의 사용자 메모리 소모: 13.5 MB, 모든 Python 3 제출 에서 100.00% 의 사용 자 를 격파 하 였 습 니 다.