-->
当前位置:首页 > 题库 > 正文内容

程序填空题:求解蓄栏保留问题(贪心法)

Luz3年前 (2021-05-10)题库576
求解蓄栏保留问题。农场有n头牛,每头牛会有一个特定的时间区间[b,e]在蓄栏里挤牛奶,并且一个蓄栏里任何时刻只能有一头牛挤奶。
现在农场主希望知道最少蓄栏能够满足上述要求,并给出每头牛被安排的方案。对于多种可行方案,输出一种即可。

```c++
#include
#include
#include
#include
#include
using namespace std;
#define MAX 1001
//问题表示
struct Cow //奶牛的类型声明
{
int no; //牛编号
int b; //活动起始时间
int e; //活动结束时间
int ans;
bool operator<(const Cow &s) const //重载<关系函数
{
if (e==s.e) //结束时间相同按开始时间递增排序
return b<=s.b;
else //否则按结束时间递增排序
return e<=s.e;
}
};
int n;
Cow A[MAX]={{0}}; //下标0不用
//求解结果表示
int ans[MAX]; //ans[i]表示第A[i].no头牛的蓄栏编号

bool cmp(const Cow &a,const Cow &b){
return a.no}

void solve() //求解最大兼容活动子集
{
sort(A+1,A+n+1); //A[1..n]按指定方式排序
memset(ans,0,sizeof(ans)); //初始化为0
int num=1; //蓄栏编号
for (int i=1;i<=n;i++) //i、j均为排序后的下标
{
if ()
{
A[i].ans=num; //第i头牛安排蓄栏num
int preend=A[i].e; //前一个兼容活动的结束时间
for (int j=i+1;j<=n;j++) //查找一个最大兼容活动子集
{
if ()
{
A[j].ans=num;
preend=A[j].e;
}
}
;
}
}
}

int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>A[i].no>>A[i].b>>A[i].e;A[i].ans=0;
}

solve();
sort(A+1,A+n+1,cmp);
for (int i=1;i<=n;i++)
printf("%d %d\n",A[i].no,A[i].ans);
return 0;
}

```
### 输入格式:

第一行输入农场牛数量n,接着的n行中输入每头牛的编号,活动起始时间和活动结束时间。

### 输出格式:
输出n行按牛编号递增排序的牛编号及蓄栏编号(编号从1开始)。

### 输入样例1:

```in
5
1 1 10
2 2 4
3 3 6
4 5 8
5 4 7
```

### 输出样例1:

```out
1 4
2 1
3 2
4 1
5 3
```





答案:
第1空:A[i].ans==0

第2空:A[j].b>preend && A[j].ans==0

第3空:num++

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。