贪心算法 – liuchuo

1033. To Fill or Not to Fill (25)-PAT甲级真题（贪心算法）

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=20), the average distance per unit gas that the car can run; and N (<= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,…N. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print “The maximum travel distance = X” where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

Sample Input 1:
50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300
Sample Output 1:
749.17
Sample Input 2:
50 1300 12 2
7.10 0
7.00 600
Sample Output 2:
The maximum travel distance = 1200.00

题目大意：汽车从杭州出发可以通过高速公路去任何城市，但是油箱的容量是有限的，路上有很多加油站，每个加油站的价格不同，为汽车设计一个从杭州到终点的最便宜的路线，Cmax表示油箱最大容量，D表示杭州到目的地的距离，Davg表示平均每单位的汽油可以让汽车行驶的距离，N表示汽车的站点数量，每个站点都会给出它的单位油价Pi和汽车站点和杭州的距离Di，求汽车从杭州到终点的最小花费，如果不能够到达，就输出汽车能够行驶的最大距离

分析：贪心算法。
0.假设增加一个目的地处的加油站，距离为目的地的距离，价格为0，考虑从0距离开始能否到达最后一个加油站的问题
1.因为先开始没有油，所以如果所有的加油站距离都没有等于0的，那么说明车哪也去不了，直接输出并return
2.将加油站按照距离dis从小到大排序
3.先去第一个加油站，设置变量nowdis表示当前所在的距离，maxdis是能够到达的最大距离，nowprice是当前的站点的价格，totalPrice是总的价格。
贪心思想：
0.寻找比自己距离远的，到能够到达的最大距离之间的加油站，看他们的油价。如果找到了更低价格的油价，就加油到刚好能到达那个加油站的距离的油，然后去那个更低价格的加油站（有更低的我一分都不想多花在别的距离上，只加到刚好满足更低价格的加油站的距离就行，那样以后的路程我就可以以更低的价格行驶啦）
1.如果找不到更低的，就找尽可能低的油价的加油站，在当前加油站加满油之后过去。因为想要让路程上使用的尽可能是低价的油，既然没有比当前更低价格的了，就让油箱加到最大值，这样能保证利益最大化，保证最大的距离使用的是便宜的油。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 99999999;
struct station {
    double price, dis;
};
bool cmp1(station a, station b) {
    return a.dis < b.dis;
}
int main() {
    double cmax, d, davg;
    int n;
    scanf("%lf%lf%lf%d", &cmax, &d, &davg, &n);
    vector<station> sta(n + 1);
    sta[0] = {0.0, d};
    for(int i = 1; i <= n; i++)
        scanf("%lf%lf", &sta[i].price, &sta[i].dis);
    sort(sta.begin(), sta.end(), cmp1);
    double nowdis = 0.0, maxdis = 0.0, nowprice = 0.0, totalPrice = 0.0, leftdis = 0.0;
    if(sta[0].dis != 0) {
        printf("The maximum travel distance = 0.00");
        return 0;
    } else {
        nowprice = sta[0].price;
    }
    while(nowdis < d) {
        maxdis = nowdis + cmax * davg;
        double minPriceDis = 0, minPrice = inf;
        int flag = 0;
        for(int i = 1; i <= n && sta[i].dis <= maxdis; i++) {
            if(sta[i].dis <= nowdis) continue;
            if(sta[i].price < nowprice) {
                totalPrice += (sta[i].dis - nowdis - leftdis) * nowprice / davg;
                leftdis = 0.0;
                nowprice = sta[i].price;
                nowdis = sta[i].dis;
                flag = 1;
                break;
            }
            if(sta[i].price < minPrice) {
                minPrice = sta[i].price;
                minPriceDis = sta[i].dis;
            }
        }
        if(flag == 0 && minPrice != inf) {
            totalPrice += (nowprice * (cmax - leftdis / davg));
            leftdis = cmax * davg - (minPriceDis - nowdis);
            nowprice = minPrice;
            nowdis = minPriceDis;     
        }
        if(flag == 0 && minPrice == inf) {
            nowdis += cmax * davg;
            printf("The maximum travel distance = %.2f", nowdis);
            return 0;
        }
    }
    printf("%.2f", totalPrice);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

const int inf = 99999999;

struct station {

double price, dis;

};

bool cmp1(station a, station b) {

return a.dis < b.dis;

}

int main() {

double cmax, d, davg;

int n;

scanf("%lf%lf%lf%d", &cmax, &d, &davg, &n);

vector<station> sta(n + 1);

sta[0] = {0.0, d};

for(int i = 1; i <= n; i++)

scanf("%lf%lf", &sta[i].price, &sta[i].dis);

sort(sta.begin(), sta.end(), cmp1);

double nowdis = 0.0, maxdis = 0.0, nowprice = 0.0, totalPrice = 0.0, leftdis = 0.0;

if(sta[0].dis != 0) {

printf("The maximum travel distance = 0.00");

return 0;

} else {

nowprice = sta[0].price;

}

while(nowdis < d) {

maxdis = nowdis + cmax * davg;

double minPriceDis = 0, minPrice = inf;

int flag = 0;

for(int i = 1; i <= n && sta[i].dis <= maxdis; i++) {

if(sta[i].dis <= nowdis) continue;

if(sta[i].price < nowprice) {

totalPrice += (sta[i].dis - nowdis - leftdis) * nowprice / davg;

leftdis = 0.0;

nowprice = sta[i].price;

nowdis = sta[i].dis;

flag = 1;

break;

}

if(sta[i].price < minPrice) {

minPrice = sta[i].price;

minPriceDis = sta[i].dis;

}

if(flag == 0 && minPrice != inf) {

totalPrice += (nowprice * (cmax - leftdis / davg));

leftdis = cmax * davg - (minPriceDis - nowdis);

nowprice = minPrice;

nowdis = minPriceDis;

}

if(flag == 0 && minPrice == inf) {

nowdis += cmax * davg;

printf("The maximum travel distance = %.2f", nowdis);

return 0;

}

printf("%.2f", totalPrice);

return 0;

}

蓝桥杯 ALGO-34 算法训练纪念品分组（贪心算法+排序）

问题描述
　　元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
　　你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
输入格式
　　输入包含n+2行：
　　第1行包括一个整数w，为每组纪念品价格之和的上限。
　　第2行为一个整数n，表示购来的纪念品的总件数。
　　第3~n+2行每行包含一个正整数pi (5 <= pi <= w)，表示所对应纪念品的价格。
输出格式
　　输出仅一行，包含一个整数，即最少的分组数目。
样例输入
100
9
90
20
20
30
50
60
70
80
90
样例输出
6
数据规模和约定
　　50%的数据满足：1 <= n <= 15
　　100%的数据满足：1 <= n <= 30000, 80 <= w <= 200
分析：排序+贪心。先从小到大排序，i、j指针分别从左到右、从右到左遍历。
如果a[i]+a[j] <= w，那么把这两个物品都放入同一组，并且同时移动指针；
否则，只能把j所指向的物品放入单独的一个组，移动j指针…直到i j把所有物品都遍历完~

分析下贪心算法的可行性：如果j物品和i物品加起来超过了w，因为j物品比j+1处的物品价值小，那么如果i不能满足加起来的条件，而i-1能满足该条件，是否会影响贪心算法的结果呢？
如果让j和i-1去组合，对于j+1，因为价值比j更大，所以就更放不进i了，所以即使交换组合方式还是不影响构成的组数的~

至于为什么循环的条件是i <= j，当i<j的时候，假设i j已经相邻，那么此时还能再比较一次i+j能否满足构成一组的条件，如果满足就会把它们放到一组，之后i j指针同时移动后i>j不能够满足进入循环的条件了；如果不满足把它们放入一组，那么j放入一组后j移动指针，使i == j，继续进入循环；
当i == j的时候，因为这个单独的物品已经没有可以组合的物品剩余了，所以此时还要进入循环进行一次 cnt++ 的计数操作~//这就是while(i <= j)的解释~~~

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int main() {
	int w, n;
	scanf("%d %d", &w, &n);
	int *a = new int[n];
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	sort(a, a+n);
	int i = 0, j = n-1, cnt = 0;
	while(i <= j) {
		if(a[i] + a[j] <= w) {
			i++;
		}
		cnt++;
		j--;
	}
	cout << cnt;
	return 0;
}

#include <iostream>

#include <algorithm>

#include <cstdio>

using namespace std;

int main() {

int w, n;

scanf("%d %d", &w, &n);

int *a = new int[n];

for(int i = 0; i < n; i++)

scanf("%d", &a[i]);

sort(a, a+n);

int i = 0, j = n-1, cnt = 0;

while(i <= j) {

if(a[i] + a[j] <= w) {

i++;

}

cnt++;

j--;

}

cout << cnt;

return 0;

}

蓝桥杯 ALGO-2 算法训练最大最小公倍数（贪心算法）

问题描述
已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。

输入格式
输入一个正整数N。

输出格式
输出一个整数，表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定
1 <= N <= 10^6。

分析:
1.如果 n <= 2, 那么最小公倍数为 n
2.如果 n 是奇数，那么最小公倍数的最大值为末尾的三个数相乘
3.如果是偶数的话，如果同时出现两个偶数肯定会不能构成最大值了，因为会被除以2~~分两种情况：
(1)如果 n 是偶数且不是三的倍数，比如8，那么跳过n-2这个数而选择 8 7 5 能保证不会最小公倍数被除以2~~所以最小公倍数的最大值为n * (n – 1) * (n – 3)
(2)如果 n 是偶数且为三的倍数，比如6，如果还像上面那样选择的话，6和3相差3会被约去一个3，又不能构成最大值了。那么最小公倍数的最大值为(n – 1) * (n – 2) * (n – 3)

#include <iostream>  
using namespace std;  
int main() {  
    long long n, ans;  
    cin >> n;  
    if(n <= 2)  
        ans = n;  
    else if(n % 2 == 1)  
        ans = n * (n-1) * (n-2);  
    else if(n % 3 == 0)  
        ans = (n - 1) * (n - 2) * (n - 3);  
    else  
        ans = n * (n - 1) * (n - 3);    
    cout << ans;  
    return 0;  
}

#include <iostream>

using namespace std;

int main() {

long long n, ans;

cin >> n;

if(n <= 2)

ans = n;

else if(n % 2 == 1)

ans = n * (n-1) * (n-2);

else if(n % 3 == 0)

ans = (n - 1) * (n - 2) * (n - 3);

else

ans = n * (n - 1) * (n - 3);

cout << ans;

return 0;

}

蓝桥杯 ADV-148 算法提高排队打水问题（贪心）

问题描述
有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2………..tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？
输入格式
第一行n，r (n<=500,r<=75)
第二行为n个人打水所用的时间Ti (Ti<=100)；
输出格式
最少的花费时间
样例输入
3 2
1 2 3
样例输出
7
数据规模和约定
其中80%的数据保证n<=10

分析：按照时间从大到小的顺序排序后即为打水的顺序~每个人依次进入队列1…r、1…r、1…r……对于前面可以排满的且不是队列最后一排的人，每排满一行，总时间等于自身打水的时间加上前面所有人打水的时间~对于每个队列的最后一个人(或者倒数第二个人)，总时间等于自身打水的时间加上前面这一列所有人打水的时间~

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int n, r;
    scanf("%d %d", &n, &r);
    int *a = new int[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a+n);
    int ans = 0;
    int cnt = n/r;
    int index = 0;
    while(cnt--) {
        for(int j = 0; j < index; j++)
            ans += a[j];
        for(int i = 0; i < r; i++)
            ans += a[index++];
    }
    while(index < n) {
        int t = index % r;
        while(t < n) {
            ans += a[t];
            t += r;
        }
        index++;
    }
    cout << ans;
    delete [] a;
    return 0;
}

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int main() {

int n, r;

scanf("%d %d", &n, &r);

int *a = new int[n];

for(int i = 0; i < n; i++) {

scanf("%d", &a[i]);

}

sort(a, a+n);

int ans = 0;

int cnt = n/r;

int index = 0;

while(cnt--) {

for(int j = 0; j < index; j++)

ans += a[j];

for(int i = 0; i < r; i++)

ans += a[index++];

}

while(index < n) {

int t = index % r;

while(t < n) {

ans += a[t];

t += r;

}

index++;

}

cout << ans;

delete [] a;

return 0;

}