Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register

此题贪心的方法不正确，求大神指点

Posted by qihongqi at 2012-12-21 19:10:41 on Problem 1083
```我开始做的贪心的思路是：在所有给定的移动组数中每次选取相容（就是不需要等待的）个数最多的为一次移动，然后再在剩下的组书中选取相容个数最多的为一次移动，。。。直到所有组都移动完，记录移动的次数即可。但是这种贪心选择在每次选相容最多的个数时有重复，这样会影响后面的选择即局部的贪心不是最优的，所以会出错

#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;
}
```

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator