快排算法解法

// NUDTer2026
//2024/4/21
#include<iostream>
#include<malloc.h>
using namespace std;

typedef struct test{
    int mass;
    float value;
}Thing;


void sort(Thing* t,int start,int end)
{
    if (start>=end)
        return;
    Thing base = t[start];
    int low = start;
    int high = end;
    while (low < high)
    {
        while (low < high and t[high].value>=base.value)
            high -= 1;
        t[low] = t[high]; //请分析这一步的操作的底层逻辑 即 这一步赋值到底是值还是指针
        while(low<high and t[low].value< base.value)
            low += 1;
        t[high]= t[low];
    }
    t[low]=base;
    sort(t,0,low-1);
    sort(t,low+1,end);
}

int main()
{
    int n, m;
    cin>> n>> m;
    Thing* thing =(Thing*)malloc(sizeof(Thing)* n);
    for (int i =0; i< n; i++)
    {
        float temp =0;
        cin>> thing[i].mass>>thing[i].value;
        thing[i].value = thing[i].value/thing[i].mass;
    }
    sort(thing,0,n-1);
    float sum = 0;
    while(m && n)
    {
        if(m>=thing[n-1].mass) {
            sum += thing[n-1].value * thing[n-1].mass;
            m -= thing[n-1].mass;
        }
        else {
            sum += thing[n-1].value * m;
            m = 0;
        }
        n-=1;
    }
    printf("%.2lf",sum);
    return 0;
}

普通排序算法

#include <iostream>
#include <algorithm>
#include <malloc.h>
using namespace std;
typedef struct GOOD
{
	double sumValue;
	double sumMass;
	double signalValue;//The avg value of mass
}good;
//使其从小到大排序
void swap(good& t1, good& t2)
{
	good temp = t1;
	t1 = t2;
	t2 = temp;
}

int main()
{
	double sumMoney = 0;
	int N,T;
	cin >> N >> T;
	good* goods = new good[N];
	for (int i = 0; i < N; i++)
	{
		cin >> goods[i].sumMass >> goods[i].sumValue;
		goods[i].signalValue = goods[i].sumValue / goods[i].sumMass*1.0;
	}


	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N - i -1; j++)
		{
			if (goods[j].signalValue > goods[j+1].signalValue)
				swap(goods[j], goods[j+1]);
		}
	}


	int remainMass = T;//剩余可用质量
	if (N == 0||T==0)
	{
		printf("%.2lf", sumMoney);
		delete[] goods;
		return 0;
	}

	while (remainMass&&N>=1)
	{
		if (remainMass >= goods[N-1].sumMass)
		{
			remainMass -= goods[N-1].sumMass;
			sumMoney += goods[N-1].sumValue;
			N--;
		}
		else if(remainMass>=1)
		{
			sumMoney += remainMass * goods[N-1].signalValue;
			remainMass -= remainMass;
		}
	}
	printf("%.2lf", sumMoney);
	delete[] goods;
	return 0;
}