C68-排队接水问题

一、最简单的排队接水问题

接水最快的人先接

#include<bits/stdc++.h>
using namespace std;

int n, a[1005], sum;

int main(){
	cin >> n;
	for (int i=1; i<=n; i++) {
		cin >> a[i]; 
	} 
	sort(a+1, a+1+n);
	
	for(int i=1; i<=n; i++){
		sum += a[i]*(n-i+1);
	}
	cout << sum;

	return 0;
}

/*
输入：
4
2 6 4 5
输出：
36
*/ 

二、升级一点的接水问题

题目描述

#include<bits/stdc++.h>
using namespace std;

struct node{
	int time;
	int idx;
}a[1005]; 
int n, sum;

bool cmp(node x, node y){
	return x.time < y.time;
} 

int main(){
	cin >> n;
	for(int i=1; i<=n; i++) {
		cin>>a[i].time;
		a[i].idx = i;
	}
	sort(a+1, a+1+n, cmp);
	
	for (int i=1; i<=n; i++) {
		cout<< a[i].idx <<' ';
		sum += a[i].time*(n-i); 
	}
	printf("\n%.2lf", sum*1.0/n); 
	
	return 0;
}

三、水壶问题

以下是暴力不能通过代码， 需要用前缀和进行优化

#include<iostream>
using namespace std;

int n, a[1005], m;
 
int main(){
	cin >> n;
	for (int i=1; i<=n; i++){
		cin >> a[i];
	}
	cin >> m;
	while (m--){
		int l, r, sum = 0;
		cin >> l >> r;
		for (int i=l; i<=r; i++) sum+=a[i];
		cout<<sum<<endl; 
	} 

	return 0;
}