算法题解(3)-贪心

#include <bits/stdc++.h>

struct mon{
    int w,v;
    double bili;
}money[110];

void swap(mon *a,mon *b){
    double t=a->bili;
    a->bili=b->bili;
    b->bili=t;

    int d=a->w;
    a->w=b->w;
    b->w=d;

    d=a->v;
    a->v=b->v;
    b->v=d;
}

void quick_sort(mon arr[],int len) {
    if (len <= 1) return;
    srand((unsigned)time(nullptr));
    const double pivot = arr[rand() % len].bili;
    int i = 0, j = 0, k = len;
    while (i < k) {
        if (arr[i].bili > pivot){
            swap(&arr[i], &arr[j]);
            i++;j++;}
        else if (pivot > arr[i].bili){
            swap(&arr[i], &arr[k-1]);
            k--;}
        else
            i++;
    }
    quick_sort(arr, j);
    quick_sort(arr + k, len - k);
}

int main(){
    int n,bag;
    scanf("%d%d",&n,&bag);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d",&money[i].w,&money[i].v);
        if (money[i].w==0) money[i].bili=0;
        else money[i].bili=1.0*money[i].v/money[i].w;
    }
    quick_sort(money,n);
    int i=0;
    double sum=0;
    while (bag>=money[i].w){
        bag-=money[i].w;
        sum+=money[i].v;
        i++;
    }
    sum+=bag*money[i].bili;
    printf("%.2lf",sum);
    return 0;
}

#include <bits/stdc++.h>

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

void quick_sort(int arr[],int len) {
    if (len <= 1) return;
    srand((unsigned)time(NULL));
    const int pivot = arr[rand() % len];
    int i = 0, j = 0, k = len;
    while (i < k) {
        if (arr[i] < pivot){
            swap(&arr[i], &arr[j]);
            i++;j++;}
        else if (pivot < arr[i]){
            swap(&arr[i], &arr[k-1]);
            k--;}
        else
            i++;
    }
    quick_sort(arr, j);
    quick_sort(arr + k, len - k);
}

void shell_sort(int arr[], int length) {
    int h = 1;
    while (h < length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                swap(&arr[j], &arr[j - h]);
            }
        }
        h = h / 3;
    }
}

int main(){
    int n;
    scanf("%d",&n);
    int guo[n+5];
    guo[n]=0;
    for (int i = 0; i < n; ++i) {
        scanf("%d",&guo[i]);
    }
    int sum=0;
    int tili;
    quick_sort(guo,n);
    for (int i = 0; i < n-1; ++i) {
        shell_sort((guo+i),n-i);
        tili=0;
        tili+=(guo[i+1]+guo[i]);
        guo[i+1]+=guo[i];
        sum+=tili;
    }
    printf("%d",sum);
}

#include <bits/stdc++.h>
#include <algorithm>

struct per {
    int index;
    int time;
}person[2000];

void swap(per *a,per *b){
    int t=a->time;
    a->time=b->time;
    b->time=t;

    t=a->index;
    a->index=b->index;
    b->index=t;
}

void quick_sort(per arr[],int len) {
    if (len <= 1) return;
    srand((unsigned)time(NULL));
    const int pivot = arr[rand() % len].time;
    int i = 0, j = 0, k = len;
    while (i < k) {
        if (arr[i].time < pivot){
            swap(&arr[i], &arr[j]);
            i++;j++;}
        else if (pivot < arr[i].time){
            swap(&arr[i], &arr[k-1]);
            k--;}
        else
            i++;
    }
    quick_sort(arr, j);
    quick_sort(arr + k, len - k);
}


int main(){
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; ++i) {
        person[i].index=i+1;
        scanf("%d",&person[i].time);
    }
    quick_sort(person,n);
    for (int i = 0; i < n; ++i) {
        printf("%d ",person[i].index);
    }
    printf("\n");
    double sum=0;
    int shijian=0;
    for (int i = 0; i < n-1; ++i) {
        shijian+=person[i].time;
        sum+=shijian;
    }
    printf("%.2lf\n",1.0*sum/n);
    //?????我卡了半天,后面的1.0*sum/n是原本就有的,sum是int类型。
    //然后本是int的sum变成double,去掉了1.0,就又过了两个，但是第一个却过不了。
    //把1.0加上，就全部过了。离谱
}