我开始做的贪心的思路是：在所有给定的移动组数中每次选取相容（就是不需要等待的）个数最多的为一次移动，然后再在剩下的组书中选取相容个数最多的为一次移动，。。。直到所有组都移动完，记录移动的次数即可。但是这种贪心选择在每次选相容最多的个数时有重复，这样会影响后面的选择即局部的贪心不是最优的，所以会出错
下面是我的代码
#include <iostream>
#include<cstring>
using namespace std;
class Room
{
public:
    int from,to;
    bool isOut;
    Room()
    {
        isOut=false;
        from=0;
        to=0;
    }
};
Room room[201];
void change(Room &r, Room &m)
{
    int f,t;
    bool tp;
    f=r.from;
    r.from=m.from;
    m.from=f;
    t=r.to;
    r.to=m.to;
    m.to=t;
    tp=r.isOut;
    r.isOut=m.isOut;
    m.isOut=tp;
}
void greedySelecter(Room rm[],int len)
{
    int i,m;
    for(i=0;i<len;i++) if(!rm[i].isOut) {rm[i].isOut=true;break;}
    for(m=i+1;m<len;m++)
    {
        if((rm[m].from-rm[i].to==1)&&rm[m].from%2==0);
        else{
            if(rm[m].from>rm[i].to) { rm[m].isOut=true;i=m;}
        }
    }
}
bool check(Room rm[],int n)
{
    int i;
    for(i=0;i<n;i++) if(!rm[i].isOut) return true;
    return false;
}
void mySort(Room rm[],int n)
{
    int i,j;
    for(i=0;i<n-1;i++)
        for(j=i+1;j<n;j++)
        {
            int k=i;
            if(rm[j].to<rm[i].to) k=j;
            change(rm[i],rm[k]);
        }
}
void init(Room rm[],int n)
{int i;
    for(i=0;i<n;i++)
    {
        rm[i].from=0;
        rm[i].to=0;
        rm[i].isOut=false;
    }
}
int main()
{
    int t;
    cin>>t;
    int n;
    while(t--)
    {
        cin>>n;
        int i;
        int count=0;
        for(i=0;i<n;i++)
        cin>>room[i].from>>room[i].to;
        mySort(room,n);
        while(check(room,n))
        {
            greedySelecter(room,n);
            count++;
        }
        cout<<count*10<<endl;
        init(room,n);
    }
    return 0;
}

• Re:此题贪心的方法不正确，求大神指点 (1989) ppen 2014-01-24 11:32:07
• Re:此题贪心的方法不正确，求大神指点 (1989) zhangshichong 2018-09-08 20:31:58