上周因为生病影响博客更新暂缓了，今天恢复更新博客
昨天晚上学习了二叉树和图，但是因为数据结构本身难度就非常大，所以只学了储存二叉树，图的方法和遍历等，还没有办法做实际的题目
于是就先复习了贪心算法，总共写了两道题目
第一道是P1223排队接水（洛谷橙题），贪心的方法很容易看出来， 但是因为输出格式是输出同学编号而不是等待时间，所以需要用到结构体，而同时增加了等待时间相同的情况，同时帮我复习了sort排序函数的cmd部分
这里还用到了fixed和setprecision函数，注意保留的小数位数
这里附上题目和我的解题代码
有 $n$ 个人在一个水龙头前排队接水，假如每个人接水的时间为 $T_i$，请编程找出这 $n$ 个人排队的一种顺序，使得 $n$ 个人的平均等待时间最小。
一个人的等待时间不包括他的接水时间。
如果两个人接水的时间相同，编号更小的人应当排在前面。
第一行为一个整数 $n$。
第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的接水时间 $T_i$。
输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。
10
56 12 1 99 1000 234 33 55 99 812
3 2 7 8 1 4 9 6 10 5
291.90
$1\le n \leq 1000$，$1\le t_i \leq 10^6$，不保证 $t_i$ 不重复。
##下面是解题代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<iomanip>
struct watert
{
int num;
double min;
};
int cmd(watert a,watert b)
{
if(a.min==b.min)
{
return (a.num<b.num);
}
else
{
return (a.min<b.min);
}
}
watert arr[100000];
int main()
{
int n;
double sum=0,average;
cin>>n;
for(int i=0;i<n;i++)
{
arr[i].num=i+1;
cin>>arr[i].min;
}
sort(arr,arr+n,cmd);
for(int i=0;i<n;i++)
{
cout<<arr[i].num<<" ";
sum+=(n-i-1)*arr[i].min;
}
average=sum/n;
cout<<fixed<<setprecision(2);
cout<<endl<<average;
return 0;
}
这里可以看到cmd中分了两种情况，第一种是等待时间不相同的情况，将等待时间1小于等待时间2视为正确，否则交换
第二种是等待时间相同的时候，将同学序号1小于同学序号2视为正确
下面这题是一道此前没有见过的贪心题目，我是不会做的，题目提示了贪心，但是还是没有想出来
下面这是我看到的题解
在一个数轴上有n条线段，现要选取其中k条线段使得这k条线段两两没有重合部分，问最大的k为多少。
最左边的线段放什么最好？
显然放右端点最靠左的线段最好，从左向右放，右端点越小妨碍越少
其他线段放置按右端点排序，贪心放置线段，即能放就放
看完之后我的最初始思路是每次在做所有比赛中寻找end最小且start符合条件的比赛
这里附上代码
#include<iostream>
using namespace std;
struct contest
{
int begin;
int end;
};
contest arr[1000000];
int main()
{
int n;
int most=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>arr[i].begin;
cin>>arr[i].end;
}
int now=0;
while(1)
{
int choice=-1;
int now1=1000000;
for(int i=0;i<n;i++)
{
if(arr[i].begin>=now&&arr[i].end<now1)
{
now1=arr[i].end;
choice=i;
}
}
if(choice>=0)
{
now=arr[choice].end;
most++;
}
else
{
break;
}
}
cout<<most;
return 0;
}
但是！！！这段代码有两个测试点TLE了！！
这其实和排序是一样的，每次寻找end最大的，并且符合条件（只是比排序多了一个判断而已），算法时间复杂度是n的平方
为了防止TLE，必须把算法空间复杂度至少降低到nlogn，而遍历所有比赛找到第一个end最小的是必须的，这里的复杂度是n，而可以看出，第二个end计算出来之后有部分比赛会被重复遍历
于是我想到了排序，按end从小到大排序，nlogn复杂度，然后遍历数组，取第一个，然后往后遍历，不符合条件就遍历下一个，符合就直接拿来用，这样只要遍历一次即可得到most，复杂度是n
所以整个算法的复杂度是nlogn
完美地解决了TLE的问题！！
z这里附上真正正确的代码
#include<iostream>
using namespace std;
#include<algorithm>
struct contest
{
int begin;
int end;
};
int cmd(contest a,contest b)
{
return a.end<b.end;
}
contest arr[1000000];
int main()
{
int n;
int most=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>arr[i].begin;
cin>>arr[i].end;
}
sort(arr,arr+n,cmd);
int now=0;
for(int i=0;i<n;i++)
{
if(arr[i].begin>=now)
{
most++;
now=arr[i].end;
}
}
cout<<most;
return 0;
}
这道题目的思路对于我个人非常有价值，强调了快速排序nlogn的神奇之处