//贪心算法，局部最优
#include<stdio.h>
int array[100001];
void quicksort(int left,int right){
	if(left > right)
	  return;
	int i,j,t;
	i = left;//左边哨兵 
	j = right;//右边哨兵 
	int temp = array[left];//设置基位 
	while(i!=j){//当左右不相等的时候进行遍历
	    while(array[j] >= temp && i < j)
		j--;
	    while(array[i] <= temp && i < j)
		i++; 
		if(i<j){
			t = array[i];
			array[i] = array[j];
			array[j] = t;
		}
	}
	array[left] = array[i];
	array[i] = temp;
	quicksort(left,i-1);
	quicksort(i+1,right);
	return;
}
int main(){
	int n;
	long long sum = 0;
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d",&array[i]);
	}    
	quicksort(0,n-1);
    for(int i=0; i<n; i++){
    	sum += array[i]*(n-i-1);
	}
	printf("%lld\n",sum);
} 

题解

这个题很好理解吧，题目上说第 i 个人装满水桶所需的时间是 t_i，花时间短的排在前面就行。

代码

#include<bits/stdc++.h>  
using namespace std;
int t[100010];
int main()
{
	int n;
	std::ios::sync_with_stdio(false);
	cin>>n;
	for(int i=0;i<n;i++) cin>>t[i];
	sort(t,t+n);
	long long sum=0;
	for(int i=0;i<n;i++) sum+=t[i]*(n-i-1);
	cout<<sum<<endl;
	return 0;
}

排序所有人打水时间，让短的先打，就节约时间，可以自己写例子试

上代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,a[100005]={0};
	long long sum=0,s=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	sort(a,a+n);
	for(int i=0;i<n-1;i++)
	{
		s+=a[i];
		sum+=s;
	}
	printf("%lld",sum);
	return 0;
}

P1072. 排队打水

题意概述

不同的人有不同的打水时间，根据他们的打水时间，用一个最优方案使得所有人的等候时间最短

题意分析

为了尽快让大家的等待时间较少，就应该把打水时间较短的放到最前面（严重怀疑这是一个排序题，或者说就是排序题），我们对打水时长做一个升序排序，然后依次计算每个人的等待时间最后累加即可。

可行代码

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
int main() {
    ll all;
    cin >> all;
    ll time[all];
    for (ll i = 0; i < all; i++)
        cin >> time[i];
    sort(time, time + all);
    ll sum = 0;
    for(ll i = 0; i < all; i++){
        sum += time[i] * (all - i - 1);
    }
    cout << sum << endl;
    return 0;
}

END

题解

思路还是简单，把打水时间从小到大进行排序即可，注意一点，在打水的人本身不算等待的时间，直接上代码：

代码

#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
int x[100000000],y[17];
char a[11],b[18];
struct Main{
	char a[20];
	int cheng;
}pp[300];
int cmp(Main x,Main y){
	return x.cheng>y.cheng;
}
int main()
{
	long long n,m,sum=0;
	cin>>n;
	m=n-1;
	for(long long i=1;i<=n;i++){
		cin>>x[i];
	}
	sort(x+1,x+1+n);
	for(long long i=1;i<=n;i++){
		sum+=x[i]*m;
		m--;
	} 
	cout<<sum<<endl;
	return 0;
}

将打水的人按从小到大排序，然后思路就很清晰了 样例:3 6 1 4 2 5 7 1 2 3 4 5 6 7 第一个人0，第二个1，第三个3，第四个6，第五个10，第六个15，第七个21 #include #include using namespace std; long long int n,sum; int s[100005],a[100005]; int main() { cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } sort(a,a+n); for(int i=0;i<n;i++) { sum+=a[i]*(n-i-1); } cout<<sum; return 0; }

很清晰的思路 需要从让人等待时间最少的人开始打水，每一轮等待的时间都为这个人打水的时间乘以剩下的人数，最后把时间加起来就行了