189 8069 5689

算法进阶指南：基本算法0x07贪心-创新互联

1.Sunscreen

传送门

成都创新互联主营莱西网站建设的网络公司,主营网站建设方案,成都app开发,莱西h5微信小程序定制开发搭建,莱西网站营销推广欢迎莱西等地区企业咨询
#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(t
2.Stall Reservations
传送门
（1）按照左端点从小到大排序
（2）维护一个优先队列，存储stall的结束时间和编号号。按照结束时间升序。
（3）每一次取队首，如果结束时间小于开始时间，修改它的结束时间。否则需要新开一个。
#include#include#include#include#include#include#include#include#include#include#include#include#include#include 
#define pii pair#define pll pair#define pil pair#define pli pair#define pdd pair#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=50010;
struct node{
	int id,x,y;
}p[N];
int ans[N],cnt;
bool cmp(node a,node b)
{
	return a.x>n;
	rep(i,0,n) p[i].id=i,cin>>p[i].x>>p[i].y;
	sort(p,p+n,cmp);
	priority_queue, greater>q;
	rep(i,0,n){
		if(q.empty()){
			ans[p[i].id]=++cnt;
			q.push({p[i].y,cnt});
			continue;
		}
		pii t=q.top();
		if(t.fi_; 
	while(_--){
		solve();
	}
	return 0;
}
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}
推广到两个组的和并：
合并两组的时候只需要将平均值大的放在前面即可。具体做法类似于并查集，先把每个点看成是独立的一组，在考虑把子节点并向父节点，在这个过程当中计算增加的花费。最终并成一个点。
#include#include#include#include#include#include#include#include#include#include#include#include#include#include 
#define pii pair#define pll pair#define pil pair#define pli pair#define pdd pair#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=1010;
struct node{
	int fa,sz,sum;
	db avg;
}S[N];
int n,r;
int find()
{
	db avg=0,res=0;
	rep(i,1,n+1){
		if(i!=r&&avg>n>>r&&n){
		int ans=0;
		rep(i,1,n+1){
			int val;
			cin>>val;
			ans+=val;
			S[i]={0,1,val,val};
		}
		rep(i,0,n-1){
			int x,y;
			cin>>x>>y;
			S[y].fa=x;
		}
		rep(i,0,n-1){
			int p=find(),fa=S[p].fa;
			ans+=S[p].sum*S[fa].sz;
			S[p].avg=-1;
			rep(i,1,n+1) if(S[i].fa==p) S[i].fa=fa;
			S[fa].sum+=S[p].sum;
			S[fa].sz+=S[p].sz;
			S[fa].avg=(db)S[fa].sum/S[fa].sz;
		}
		cout<>_; 
	while(_--){
		solve();
	}
	return 0;
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
            

            本文名称：算法进阶指南：基本算法0x07贪心-创新互联            

            文章网址：http://cdxtjz.com/article/hoied.html

其他资讯