青藤 贪心（2）

青藤 贪心（2）

第一题 种树
题目大意： 给路被分为n个段，每个路段只种一棵树，现在有h组建议，让b到e路段种t棵树，问最少种几棵树？
分析： 还是用右端点排序，并且一定要种在路段的后面，因为种在后面很可能被后面的路段所应用，每次还要把这个路段扫描一遍，看前面有没有种上。我一开始还RE了，是因为把代表路段数的i写成了k。
代码：

#include <bits/stdc++.h>
using namespace std;
struct jg {
    int b, e, t;
} a[5001];
bool f[30001];
bool cmp(jg a, jg b) {
    if (a.e == b.e)
        return a.b < b.b;
    else
        return a.e < b.e;
}
int main() {
    int n, h, ans = 0;
    cin >> n >> h;
    for (int i = 1; i <= h; i++) cin >> a[i].b >> a[i].e >> a[i].t;
    sort(a + 1, a + h + 1, cmp);
    for (int i = 1; i <= h; i++) {
        for (int j = a[i].b; j <= a[i].e; j++)
            if (f[j] == 1)
                a[i].t--;
        for (int k = a[i].e; k >= a[i].b; k--) {
            if (f[k] == 0 && a[i].t > 0) {
                ans++;
                f[k] = 1;
                a[i].t--;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

第二题 喷水装置
题目大意： 长 米，宽 米的草坪里装有 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各w/2.0米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。
让你求最少打开几个装置让所有草坪都浇到。如果不能则输出-1。

分析： 要求最少打开装置，先看这些圆，我把这些圆与边界接触的地方画上，那么这道题就成了最小区间覆盖。还有问题这区间的边界怎么求呢？这就运用到了数学上的勾股定理:

把圆心当做直角相交的点，那么w/2.0就是其中的一条直角边，而另一条是圆的半径，就可以求出区间了。一开始我输出的全是-1，原来是求区间时，循环变量i没更新，导致区间没求全。
代码：

#include<bits/stdc++.h>
using namespace std;
struct jg
{
	double l,r;
}a[20000];
bool cmp(jg a,jg b)
{
	return a.l<b.l;
}
int x[20000],r[20000];
void work()
{
	int n,l,w,i=1,tot=0,ans=0;
	cin>>n>>l>>w;
	for(int j=1;j<=n;j++) scanf("%d %d",&x[j],&r[j]);
	while(i<=n)
	{
		if(r[i] <= w/2.0)
		{
			i++;
			continue;
		} 
		tot++;
		a[tot].l=x[i]-sqrt( r[i]*r[i] - (w/2.0) * (w/2.0));
		a[tot].r=x[i]+sqrt( r[i]*r[i] - (w/2.0) * (w/2.0));
		i++;
		
	}
	sort(a+1,a+tot+1,cmp);
	i=1;
	double m,cur=0;
	while(i<=tot)
	{
		m=a[i].r; 
		while(i+1<=tot && a[i+1].l<=cur)
		{
			i++;
			m=max(m,a[i].r);
		}
		if(a[i].l>cur) 
		{
			cout<<-1<<endl;
			return;
		}
		cur=m;
		ans++;
		if(cur>=l)
		{
			cout<<ans<<endl; 
			return;
		}
		i++;
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--) work();
    return 0;
}

第三题 智力大冲浪
题目大意： 先给你m元钱，再给你n个时段，有n个游戏，每个游戏要在ti的时间之前完成。不然就扣除mi的钱。问最多能得多少钱？
分析： 先排钱，再根据时间来，最好放在与后面，还有放了的打标记。
代码：

#include<bits/stdc++.h>
using namespace std;
bool f[505];
struct jg
{
	int m,t;
} a[505];
bool cmp(jg a,jg b)
{
	return a.t>b.t;
}
int main()
{
	int c,n,k=0;
	cin>>c>>n;
	for(int i=1;i<=n;i++) cin>>a[i].m;
	for(int i=1;i<=n;i++) cin>>a[i].t;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		k=0;
		{	
			for(int j=a[i].m;j>=1;j--)
			{
				if(f[j]==0)
				{
					f[j]=1;
					k=1;
					break;
				}
			}	
		}
		if(k==0) c=c-a[i].t;
	}
	cout<<c<<endl;
	return 0;
} 

第四题 数列极差
题目大意： 每次擦去其中的两个数a和b，然后在数列中加入一个数 ，如此下去直至黑板上剩下一个数为止，在所有按这种操作方式最后得到的数中，最大的为max，最小的为min， 则该数列的极差定义为max-min。
分析： 第一次求max，可以先排大到小，然后每次去最小的两个数来求，最后放进去排序，min也是一样。还有要开long long。
代码：

#include<bits/stdc++.h>
using namespace std;
long long a[100000],b[100000];
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	long long n,tmp,s;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	 } 
	sort(a+1,a+n+1,cmp);
	for(int i=n;i>=1;--i)
	{
		tmp=a[i]*a[i-1]+1;
		int j=i-1;
		a[j]=tmp;
		sort(a+1,a+j+1,cmp);
	}
	sort(b+1,b+n+1);
	for(int i=n;i>=1;--i)
	{
		tmp=b[i]*b[i-1]+1;
		int j=i-1;
		b[j]=tmp;
		sort(b+1,b+j+1);
	}
	//cout<<a[1]<<endl<<b[1]<<endl; 
	cout<<abs(a[1]-b[1])<<endl;
	return 0;
 }