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

Re:此题贪心的方法不正确,求大神指点

Posted by zhangshichong at 2018-09-08 20:31:58 on Problem 1083
In Reply To:此题贪心的方法不正确,求大神指点 Posted by:qihongqi at 2012-12-21 19:10:41
> 我开始做的贪心的思路是:在所有给定的移动组数中每次选取相容(就是不需要等待的)个数最多的为一次移动,然后再在剩下的组书中选取相容个数最多的为一次移动,。。。直到所有组都移动完,记录移动的次数即可。但是这种贪心选择在每次选相容最多的个数时有重复,这样会影响后面的选择即局部的贪心不是最优的,所以会出错
> 下面是我的代码
> #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:

Home Page   Go Back  To top


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