-
防晒
原题链接
我们首先将奶牛可以承受的最小值,递减排序,也就是降序排列,然后将防晒霜固定的值,递减排序,还是降序排列.
对于每头奶牛，扫描一遍所有防晒霜，在这头奶牛能用的防晒霜里找SPF最大的使用
注意:降序排序,保证对于每一头牛而言,它用的是,可以使用的最差的防晒霜,因为值越小的防晒霜,有可能让更多的牛使用.而升序排列,就恰好反了.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N=3500;
int n,m;
struct node
{
int spf,cover;
}a[N];
struct node2
{
int min_spf,max_spf;
}b[N];
bool cmp1(node2 a,node2 b)
{
return a.min_spf>b.min_spf;
}
bool cmp2(node a,node b)
{
return a.spf>b.spf;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d%d",&b[i].min_spf,&b[i].max_spf);
sort(b,b+n,cmp1);
for(int i=0;i<m;i++)
scanf("%d%d",&a[i].spf,&a[i].cover);
sort(a,a+m,cmp2);
int ans=0;
for(int i=0;i<n;i++)//枚举奶牛
{
for(int j=0;j<m;j++)//枚举防晒霜
{
if(a[j].spf>=b[i].min_spf&&a[j].spf<=b[i].max_spf&&a[j].cover)
{
ans++;
a[j].cover--;
break;//枚举下一头奶牛
}
}
}
printf("%d\n",ans);
return 0;
}
-
畜栏预定
原题链接
贪心+小根堆
维护一个小根堆，记录当前每个畜栏安排进去的最后一头牛
依次对于每头牛，与小根堆堆顶比较，若不小于畜栏最后一头牛结束吃草的时间，则加入，如果这样的畜栏不存在，则为其新建一个畜栏
时间复杂度为：O(NlogN)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int>PII;
const int N=50010;
int n;
int id[N];//牛对应其牛栏号
pair<PII,int>cow[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int l,r;
scanf("%d%d",&l,&r);
cow[i]={{l,r},i};//第i号牛的进与出
}
sort(cow,cow+n);//按照左端点排序，一个一个加
priority_queue<PII,vector<PII>,greater<PII> >heap;
int num=1;
heap.push({cow[0].first.second,num});//0号牛最晚结束时间，即其牛栏号
id[cow[0].second]=1;//0号牛对应栅栏1号
//往里面放牛
for(int i=1;i<n;i++)
{
int l=cow[i].first.first,r=cow[i].first.second,cowid=cow[i].second;
if(l>heap.top().first)//若这只牛能放进这里面
{
int t=heap.top().second;//记录一下牛栏号
heap.pop();//此牛栏更新最晚结束时间
heap.push({r,t});
id[cowid]=t;
}
else//新建牛栏
{
heap.push({r,++num});
id[cowid]=num;
}
}
cout<<heap.size()<<endl;
for(int i=0;i<n;i++)
cout<<id[i]<<endl;
return 0;
}
-
雷达设备
原题链接
由勾股定理可知，将所有小岛转化成区间后，问题转化为：给定 n 个区间，在 x 轴上选择尽量少的点，使得所有区间至少包含一个点。
算法步骤：
将所有区间按右端点从小到大排序；
依次考虑每个区间：如果当前区间包含最后一个选择的点，则直接跳过；如果当前区间不包含最后一个选择的点，则在当前区间的右端点的位置选一个新的点；
时间复杂度:
计算每个坐标所对应的区间，需要 O(n) 的计算量；
将所有区间排序需要 O(nlogn) 的计算量；
扫描所有区间需要 O(n) 的计算量；
所以总共的时间复杂度是 O(nlogn)。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1005;
typedef pair<double,double>PDD;
double INF=0x3f3f3f3f;
int n,r;
PDD seg[N];
int main()
{
cin>>n>>r;
bool success=true;
for(int i=0;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(y>r)
{
success=false;
break;
}
auto len=sqrt(r*r-y*y);
seg[i]={x+len,x-len};
}
if(!success)
{
printf("-1\n");
}
else
{
sort(seg,seg+n);//按照尾边排序
int res=0;//统计雷达数
double last=-INF;
for(int i=0;i<n;i++)
{
if(seg[i].second>last)
{
res++;
last=seg[i].first;
}
}
cout<<res;
}
return 0;
}
