贪心习题

一.有n个正整数，将它们连接成一排，组成一个最大的多位整数。例如 n = 3时，3个整数13，312，343

连成的最大整数为 34331213；又如 n = 4 时，4个整数 7，13，4，246连成的最大整数为 7424613。要

求输入 n 个正整数后，输出连成的最大整数。

题解：先把整数转换为字符串，然后比较比较 a+b 和 b+a。如果 a+b > b+a，就把 a 排在 b 前面，反之把

b 排在 a 前面。

 1 //设 s 为将读入的 n 个整数转换为字符串后的字符串数组。
 2   for(int i = 0; i < n - 1; i ++)
 3   {
 4       for(int j = i + 1; j < n; j++)
 5       {
 6           if(strcmp(strcat(s[i],s[j]),strcat(s[j],s[i])) < 0)
 7               SwapStr(s[i],s[j]);  
 8       }
 9      for(int i = 0; i < n; i++)
10          printf("%s",s[i]);
11  }

二.有n个顾客同时等待一项服务。顾客 i 需要的平均符外时间为 t_i , 1<=i<=n。如何安排n个顾客的服务次序，才

能使平均等待时间最少？平均等待时间是n个顾客等待服务时间之和除以n。

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 double greedy(vector<int>x)
 6 {
 7     int n = x.size();
 8     sort(x.begin(),x.end());
 9     for(int i = 1; i < n; i++)
10         x[i] += x[i-1];
11     double t = 0;
12     for(int i = 0; i < n; i++)
13         t += x[i];
14     t /= n;
15     return t;
16 }
17 int main()
18 {
19     int n;
20     int i;  //等待服务的顾客人数
21     int a;
22     int t;  //平均服务时间
23     vector <int> x;
24     cout<<"Please input the num of the customer:"<<endl;
25     cin>>n;
26     cout<<"Please input the need service times of each customer:"<<endl;
27     for(i = 1; i <= n; i++)
28     {
29         cout<<"No."<<i<<endl;
30         cin>>a;
31         x.push_back(a);
32     }
33     t = greedy(x);
34     cout<<"the least average waiting time is:"<<t<<endl;
35     return 0;
36 }

三.设 x₁,x₂..... x_n 是实直线上的 n 个点。用固定长度的闭区间覆盖这 n 个点, 至少需要多少个

这样的固定长度的闭区间？给定 n 个点及其闭区间长度 k。

//point[]: n 个点的整数坐标，传入前由小到大排好序
//k:闭区间的长度
int Get_solve(int p[], int n, int k)
{
    int sum = 1;
    for(int i = 1,t=p[0]; i < n; i++)
    {
        if(p[i] - t > k)
        {
            sum++;
            t = p[i];
        }
        
    }
}