题目

链接：https://ac.nowcoder.com/acm/contest/121952/D
来源：牛客网

本来想放照片的，不知道为啥放不进去，所以放了链接

解释

假如我是小红，我和小紫在玩这个游戏，面前有一堆石头，我一次可以拿一堆，但是小紫一次只能从每一堆里拿一个，但是我想赢，我得多拿一点。这么多堆，我为了多赢，我当然要从最多的开始拿。（最优解解释）

小红拿了一堆之后，小紫再从剩下的每一堆里拿一个，这里为一轮。假设有一个计次器count，没进行一轮，count就加一，此时此刻count不就变成了每一堆小紫拿的个数吗。第二轮，小红从剩下的最多堆（也就是倒数第二堆）里拿的时候，这一堆的个数就变成了原来的个数-1。换言之，以后小红拿的每一堆的个数都是原来的个数-进行的轮数。那么什么时候结束呢？一种情况是当小红这一轮的拿的最多堆个数变成0了（比这堆少的肯定是0），还有一种情况，小红刚好拿了最后一堆。

思路就是如此。

代码

#include <stdio.h>

void swap(int *a,int *b){
    int t;
    t=*a;
    *a=*b;
    *b=t;
}

int partition(int arr[],int left,int right){
    int i=left+1;
    int j=right;
    int p=arr[left];
    while(i<=j){
        while(i<=j&&p>arr[i])
            i++;
        while(i<=j&&p<arr[j])
            j–;
        if(i<=j){
            swap(&arr[i],&arr[j]);
            i++;
            j–;
        }
    }
    if(arr[j]<=p)
        swap(&arr[left],&arr[j]);
    return j;    
}

void quicksort(int arr[],int left,int right){
    if(left<right){
        int pi=partition(arr,left,right);
        quicksort(arr,left,pi-1);
        quicksort(arr,pi+1,right);
    }
}//此处为快速排序，可以用cpp里的sort大法实现

int main(){
    int n;
    long long int sum=0;
    int count=0;
    scanf(“%d”,&n);
    int arr[n];
    for(int i=0;i<n;i++){
        scanf(“%d”,&arr[i]);
    }
    quicksort(arr,0,n-1);//先排序
    for(int i=n-1;i>=0;i–){//从最多的开始的遍历
        if(arr[i]-count<=0){
            break;//这一轮的最多堆变成0了，循环结束。
        }
        sum+=(arr[i]-count);
        count++;
    }
    printf(“%lld”,sum);
}