scanf("%d %d",&d[i].l,&d[i].r); if(d[i].l>d[i].r) swap(d[i].l,d[i].r); }
sort(d,d+n,cmp);//按纵坐标升序排列 last=d[0].r;//记录当前线段被覆盖的最大坐标值
for(int i=1;i<n;i++) { if(d[i].l<=last && d[i].r>=last)//线段 d[i]的右坐标在 last 之后， 左坐标在 Last 之前的情况，即产生了覆盖。此时还要更新 last 坐标
} cout<<n.substr(0,l-s+x)<<endl;//只打印剩下的左边 l-(s-x)个数字 } return 0; } 2. #include<iostream> #include<cstdio> #include <algorithm> using namespace std; struct point {
课程实验报告
课程名称 算法分析与设计 班级 计算 161 实验日期
姓名
何严鸿
学号 20160701 实验成绩 9
实验名称
实验 5：贪心算法的应用
实
1．理解贪心算法的概念；
验
目
2．掌握贪心算法的基本思想。
的
及
要
求
实
操作系统：Windows
验
环
IDE：Visual C++
境
（1）删数问题
2018/5/06
{
length=d[i].r-d[i-1].l; last=d[i].r; } else if (d[i].r<=last) //线段 d[i]的右坐标在 last 之内，不产生覆盖 continue; else if (d[i].l>=last) //线段 d[i]的左坐标在 Last 之后，此时 last 之后的部分不会对之前的部分产生影响，更新 last 坐标。length 的值加上之 前的部分 { last=d[i-1].r; length=length+d[i].r-d[i].l; } } cout<<last<<endl; return 0; }
(4)把子问题的局部最优解合成原来问题的一个解。
实现该算法的过程如下：
(1)从问题的某一初始解出发。
(2)while 能向给定总目标前进一步。
(3)求出可行解的一个解元素。
(4)由所有解元素组合问题的一个可行解。
1.
附
录
#include<iostream>
#include<string>
using namespace std;
int main()
{
string n; int s,i,x,l,m; while(cin>>n>>s) {
i=-1,m=0,x=0; l=n.length(); while(x<s&&m==0)
{ i++; if(n[i]>n[i+1])//出现递减,删除递减的首数字 { n=n.erase(i,1); x++;// x 统计删除数字的个数 i=-1;//从头开始查递减区间 } if(i==l-x-2&&x<s) m=1;//已经无递减区间,m=1 脱离循环
出这些线段一共覆盖了多大的长度。
输入：
4//表示输入的线段个数
2 5//线段起始坐标 线段终止坐标
67
13
34
输出：
5
1.
调
试过程源自2.及实验
结
果
经过这次实验，对贪心法有了更深的了解。
总
贪心算法的基本思路如下：
结
(1)建立数学建模来描述问题。
(2)把求解的问题分成若干个问题。
(3)对每一子问题求解，得到子问题的局部最优解。
int l,r; }d[1100006];
bool cmp(const struct point &a,const struct point &b) {
return a.r<b.r; }
int main() {
int n,a; int last; int length=0;//记录线段覆盖长度
cin>>n; for(int i=0;i<n;++i) {
问题描述：给定 n 位正整数 a，去掉其中任意 k≤n 个数字后，剩下的数字
按原次序排列组成一个新的正整数。对于给定的 n 位正整数 a 和正整数 k，设
实
验
计一个算法找出剩下数字组成的新数最小的删数方案。
内
输入（第一行为 a，第二行为 k）：
容
657943148
3
输出：
543148
（2）线段覆盖
问题描述：在一维空间中告诉你 N 条线段的起始坐标与终止坐标，要求求