贪心（未完待续）

贪心算法是指对问题求解时，总是做出目前最优的选择。

而不从整体加以考虑，他做出的是当前意义上的最优解。

能够进行贪心必须保证对局部的最优解能够得到全局最优解。

当前的状态影响不到以后的状态。

思想

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

感觉贪心算法没有一个固定的过程，他仅仅是一种处理问题的思想。

几个例题：

【问题描述】
有n个人排队到r个水龙头去接水，他们装满水桶的时间t1，t2，…，tn 为整数且各不相等，

应如何安排他们的打水顺序才能使他们花费的总等待时间最少？(自己接水等的时间也要算)

思路：让接水时间少的人排在前面，我们可以举一个简单的栗子：

有3个人接水，一个水龙头，时间分别为10,5,1；

如果让时间长的排在前面，等待时间分别为0,10,15；

如果改变顺序，则等待时间为0,1,6；

自然，后者更快，用数学可以证明这一结论

：
设有N个人在分别同一水龙头下打水，时间分别为T1，T2，T3……TN；

容易看出第i个人打水的时间为他等待的时间和打水的时间，他前面有i-1个人打水，则他共花时间T(i)=T1+T2+T3+……+Ti；

则所有人打水时间为∑ T(i),i从1到N;

则可以看出时间和为:N*T1+(N-1)*T2+(N-2)*T3+……+1*TN；

则越靠前被计算的次数越多，则应该让时间少的靠前打水；

此结论得证；

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct node
{
    int a,b;
    operator < (const node &ba) const
    {
        return a<ba.a;
    }
};

int w[151][151];
int m,n;
node s[15111];
int wait[151];

int main()
{
    int i,j,sum=0;
    cin>>m>>n;
    for(i=1;i<=m;++i)
        cin>>s[i].a;
    sort(s+1,s+i);
    for(i=1;i<=m;++i)
    {
        w[i%n+1][0]++;
        w[i%n+1][w[i%n+1][0]]=i;
        wait[i%n+1]+=s[i].a;
        sum+=wait[i%n+1];
    }
    for(i=1;i<=n;++i)
        cout<<wait[i]<<' ';
    cout<<endl<<sum<<endl;
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=w[i][0];++j)
            cout<<w[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}

代码

2、

键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N 和S，寻找一种方案使得剩下的数字组成的新数最小。

输入数据均不需要判错。

输出组成的新的正整数。（N不超过240位）

输入描述 Input Description

第一行，输入一正整数N（N<=10240），表示要删的数；

第二行，输入一正整数S，表示删去的个数，当然S小于N的位数。

输出描述 Output Description

仅一行，输出删数后形成的最小数。

样例输入 Sample Input

【1】

5768

【2】

8796542

样例输出 Sample Output

【1】

568

【2】

542

数据范围及提示 Data Size & Hint

1<=N<=10240

1<=S<=239

思路：用字符串存储整数，然后循环N次，每次找出一个数，用string类型的函数erase删除；

　　最后去掉多余的0，输出，记得在去0时一定要至少留下一个数;

#include<iostream>
#include<string>
#include<cstdlib>
using namespace std;
int main()
{
    string s;
    int n,sum=0;
    cin>>s>>n;
    int i;
    while(n--)
    {
        i=0;
        while(i<s.size()&&s[i+1]>=s[i])
            ++i;
        s.erase(i,1);
    }
    int j=0;
    while(s[0]=='0'&&s.size()>1)s.erase(0,1);
    cout<<s;
    return 0;
}

代码