杭电ACM习题1004

68 阅读 0 评论 45 点赞

我是靠谱客的博主正直凉面，最近开发中收集的这篇文章主要介绍杭电ACM习题1004，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

（1）简单题意：

每次输入一个整数n，代表今天播放的电视节目数量；然后输入n对数据（x,y）,x是起始时间，y是结束时间，然后运用贪心算法选择最优方案：能够看到最多的完整的节目是多少个？（所有数据具为整数）

（2）解题思路：

我们可以用一个结构体数组做所欲输入数据的存储，然手对结束时间进行从小到大的排序，另j=0,从i=1开始，第i个节目的开始时间若小于j的结束时间，则j=i,i++；然后可以看得节目+1。用此循环，可得最优解。

（3）感想：

贪心算法的思路就是由局部最优到全局做鱼最优，所以对待一道贪心算法的题目，我们首先重点就是找到贪心点，然后根据贪心点做出贪心的局部短=算法，用循环或者递归等手段，实现全部最优。

（4）代码：

#include<iostream>
#include <algorithm>
using namespace std;
struct node
{
int st; //起始时间
int et; //结束时间
bool operator <(const node &x)//重定义<；
{
  if (et == x.et)
   return st<x.st;
  else
   return et<x.et;
}
}q[100];

int main()
{
int n;
int i, j;
while (cin>>n && n != 0)
{
  for (i = 0; i<n; i++)
  {
   cin >> q[i].st;
   cin >> q[i].et;
  }
  sort(q, q + n);//对结构体数组按照结束时间从小到大排序；
  int ans = 1;
  int j = 0; //第一个最早结束的节目必然要被选中
  for (i = 1; i<n; i++)
  {
   if (q[i].st >= q[j].et)
   {
    ans++;
    j = i; //更新到当前刚选中节目的下标
   }
  }
  cout << ans << endl;
}
return 0;
}