传送门
#includeusing namespace std;
const int N=2510;
paira[N],b[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>a[i].first>>a[i].second;
for(int i=1;i<=m;++i) cin>>b[i].first>>b[i].second;
sort(a+1,a+1+n);
sort(b+1,b+1+m);
int ans=0,j=0;
priority_queue, greater>q;
for(int i=1;i<=m;++i){
while(j<=n&&a[j].first<=b[i].first) q.push(a[j].second),++j;
while(!q.empty()&&b[i].second>0){
int t=q.top();
q.pop();
if(t2.Stall Reservations传送门
(1)按照左端点从小到大排序
(2)维护一个优先队列,存储stall的结束时间和编号号。按照结束时间升序。
(3)每一次取队首,如果结束时间小于开始时间,修改它的结束时间。否则需要新开一个。
#include#include#include#include#include#include#include#include#include#include
3.Radar Installation传送门
转化为用最少的点覆盖线段问题。
#include#define rep(i,a,b) for (register int i=a;ib;--i)
#define pdd pair#define db double
#define pii pair#define se second
#define fi first
#define MEM(a,x) memset(a,x,sizeof(a))
#define endl '\n'
typedef long long LL;
using namespace std;
const int N=1010;
pdd p[N];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,d;
while(cin>>n>>d){
if(n==0&&d==0) break;
db x,y;
bool f=1;
rep(i,0,n){
cin>>x>>y;
if(y>d) f=0;
p[i].fi=x-sqrt((db)d*d-y*y),p[i].se=x+sqrt((db)d*d-y*y);
}
if(!f){
cout<<-1<4.国王的游戏传送门1
传送门2
按照每个大臣左手右手乘积升序排列。
python版本(不用写高精):
def cmp(x):
return x[0]*x[1];
n=int(input())
nw,_=map(int,input().split(' '))
L=[]
for i in range(n):
a,b=map(int,input().split(' '))
L.append([a,b])
L.sort(key=cmp)
ans=0
for i in L:
ans=max(ans,nw//i[1])
nw*=i[0]
print(ans)
c++版本:
#includeusing namespace std;
const int N=1010;
static const int BASE=10;
static const int WIDTH=8;
struct node{
int l,r;
}mst[N];
bool cmp(node a,node b)
{
return a.l*a.rs;
BigInt(long long num=0){*this=num;}
BigInt operator = (long long num){
s.clear();
do{
s.push_back(num%BASE);
num/=BASE;
}while(num>0);
return *this;
}
bool operator< (const BigInt& b) const {
if(s.size()!=b.s.size()) return s.size()=0;i--){
if(s[i]!=b.s[i]) return s[i]=0;i--){
out<c;
long long r=0;
for(int i=a.s.size()-1;i>=0;i--){
r=r*10+a.s[i];
c.push_back(r/b);
r%=b;
}
reverse(c.begin(),c.end());
while(c.size()>1&&c.back()==0) c.pop_back();
return c;
}
int main()
{
int n,a,b;
cin>>n;
cin>>a>>b;
for(int i=0;i>mst[i].l>>mst[i].r;
sort(mst,mst+n,cmp);
BigInt pro=1ll*a*mst[0].l,ans=1ll*a/mst[0].r;
for(int i=1;i5.Color a Tree传送门
y总的视频讲解,讲得超级超级清楚
1.如果一个点的父节点已经被染色了,下一步一定会选择它子节点中大的,这两个点的先后次序就被确定了。
2.考虑三个点x,y,z。若x是y的父节点,y是权值大的子节点,y一定是在x之后染色。现在需要确定x和z的先后顺序。
先染x:s1=x+2y+3z;先染z:s2=z+2*x+3*y。
若先选x最优,即s1-s2<0,需要满足:![z<\frac{x+y}{2}](https://latex.codecogs.com/gif.latex?z%3C%5Cfrac%7Bx+y%7D%7B2%7D)
推广到两个组的和并:
![](/upload/otherpic18/e4e470a8a1d74d61875c2795bf778a81.jpg)
合并两组的时候只需要将平均值大的放在前面即可。具体做法类似于并查集,先把每个点看成是独立的一组,在考虑把子节点并向父节点,在这个过程当中计算增加的花费。最终并成一个点。
#include#include#include#include#include#include#include#include#include#include
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
当前题目:算法进阶指南:基本算法0x07贪心-创新互联
分享地址:http://bjjierui.cn/article/hoied.html