贪心杂选

自用笔记算法

贪心杂选

HDU 4296

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

有n个板，每个板有重量x和强度y两个属性，把板叠在一起，对于每个板有个PDV值，计算方式为这个板上面的板的重量和减去这个板的强度，
对于每种叠放方式，取这个叠放方式中所以板中PDV值最大的值为代表值，问所有叠放方式中最小的代表值为多少。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<algorithm>
#define LL long long
using namespace std;
struct node
{
	int w,s;
}a[100050];
int cmp(node x,node y)
{
	return x.w-y.s<y.w-x.s; //转换为x.s-y.w<y.s-x.w 可以理解为x还能承受的重量小于y
}                           //即还能承受更多的放下面
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
			scanf("%d%d",&a[i].w,&a[i].s);
		sort(a+1,a+1+n,cmp);
		LL ans=0,sum=0;
		for(int i=1;i<=n;i++)
		{
			ans=max(ans,sum-a[i].s);
			sum+=a[i].w;
		}
		printf("%I64d\n",ans);
	}
	return 0;
}

HDU 4310

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

Dota游戏中有n组敌人，每次攻击一个敌人会使这个敌人的HP减1，
但是同时你的英雄的DPS（开始是是无穷的）的值会减少，减少值为所有在当前回合仍存活的敌人的DPS总和，若敌人的HP<=0会在这一回合结束后死亡
要求将所有的敌人都消灭后你的英雄的DPS剩余的最多，即求耗费的DPS的值最少。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct node
{
	int dps,hp;
}hero[25];
int cmp(node x,node y)
{
	return x.hp*y.dps<y.hp*x.dps;   //按照攻击力/血量降序排列
}                                   //换成乘积的形式避免了小数
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int n;
	while(cin>>n)
	{
		int ans=0,sum=0;
		for(int i=1;i<=n;i++)
		{
			cin>>hero[i].dps>>hero[i].hp;
			sum+=hero[i].dps;
		}
		sort(hero+1,hero+1+n,cmp);
		for(int i=1;i<=n;i++)
		{
			ans+=sum*hero[i].hp;
			sum-=hero[i].dps;
		}
		cout<<ans<<endl;
	}
	return 0;
}

HDU 5661

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

给出范围a-b和c-d 要求在这两个范围中分别找出一个数字 要求这两个数字的异或最大

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#define LL long long
using namespace std;
LL a,b,c,d;
int is_ok(LL x,LL y,int p)  //必须满需原本的x和y小于上限
{                           //x和y加上移动的位置后必须大于下限
	LL rx=x+(1LL<<p)-1;     //才返回1 否则返回0
	LL ry=y+(1LL<<p)-1;
	if(x>b||rx<a) return 0;
	if(y>d||ry<c) return 0;
	return 1;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>a>>b>>c>>d;
		LL x=0,y=0;
		for(int i=61;i>=0;i--)      //先从y判断 再判断x 都不满足xy一起加 x和y的顺序可改变
		{                        //实际可理解为：先让y的某位由0边1 y变了那么x不能变 1^0=1才是最优
			if(is_ok(x,y+(1LL<<i),i))    //若y的某位不能变1 那么x变1 也能保证1异或0是最优解
				y+=(1LL<<i);             //若xy均不满足一个1一个0就一起变 继续进行后面位数的判断
			else if(is_ok(x+(1LL<<i),y,i))
				x+=(1LL<<i);
			else if(is_ok(x+(1LL<<i),y+(1LL<<i),i))
			{
				x+=(1LL<<i);
				y+=(1LL<<i);
			}
			else;
		}
		cout<<(x^y)<<endl;
	}
	return 0;
}

HDU 1789

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

Ignatius有N项作业要完成。每项作业都有限期，如果不在限期内完成作业，期末考就会被扣相应的分数。给出测试数据T表示测试数，每个测试以N开始
（N为0时结束），接下来一行有N个数据，分别是作业的限期，再有一行也有N个数据，分别是若不完成次作业会在期末时被扣的分数。求出他最佳的作业
顺序后被扣的最小的分数。（每个作业费时一天）。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int vis[10050];
struct node
{
	int d,re;
}c[10050];
int cmp(node x,node y)    //按照减分大小从高到低排序 减分相同期限由高到低排
{
	if(x.re==y.re)
		return x.d>y.d;
	return x.re>y.re;
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int t;
	cin>>t;
	while(t--)
	{
		int n,j;
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>c[i].d;
		for(int i=1;i<=n;i++)
			cin>>c[i].re;
		memset(vis,0,sizeof(vis));   //可看作hash表
		sort(c+1,c+1+n,cmp);
		int ans=0;
		for(int i=1;i<=n;i++)    //类似与hash表存储的原理
		{                        //对于每门课 从减分高的开始 把期限放到对应的vis数组中
			if(vis[c[i].d]==1)   //若vis中该位置已经放了数字 继续向前判断直到找到空位置或未找到
			{
				for(j=c[i].d-1;j>=1;j--)
				{
					if(!vis[j])
					{
						vis[j]=1;
						break;
					}
				}
				if(j==0)       //如果没有找到 那么ans加上该课程的减分值
					ans+=c[i].re;
			}
			else
				vis[c[i].d]=1;
		}
		cout<<ans<<endl;
	}
	return 0;
}

HDU 4864

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

有n个机器，m个任务。每个机器至多能完成一个任务。对于每个机器，有一个最大运行时间xi和等级yi，对于每个任务，也有一个运行时间xj和等级yj
只有当xi>=xj且yi>=yj的时候，机器i才能完成任务j，并获得500xj+2yj金钱。问最多能完成几个任务，当出现多种情况时，输出获得金钱最多的情况

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
struct node
{
	int time,l;
}machine[100050],test[100050];
int cmp(node x,node y)         //按照时间从高到低贪心 时间相同按照等级从高到低贪心
{
	if(x.time==y.time)
		return x.l>y.l;
	else
		return x.time>y.time;
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int n,m;
	while(cin>>n>>m)
	{
		int vis[105];
		for(int i=1;i<=n;i++)
			cin>>machine[i].time>>machine[i].l;
		for(int i=1;i<=m;i++)
			cin>>test[i].time>>test[i].l;
		sort(machine+1,machine+1+n,cmp);
		sort(test+1,test+1+m,cmp);
		LL ans=0;                      //注意sum一定是LL型 WA数发
		int num=0;
		memset(vis,0,sizeof(vis));
		for(int i=1,j=1;i<=m;i++)      //遍历每个任务 先找出所有比该任务时间多的机器
		{                              //再在这些机器中找到等级比任务高且最接近的 该机器清零
			for(;j<=n;j++)          //注意j不要从头遍历 不然清零的机器会重新使用而WA
			{                       //用到了贪心的思想 下一个任务的时间肯定比上一个少 所以从上一个j出发
				if(machine[j].time>=test[i].time)     //依然会得到正确的结果
					vis[machine[j].l]++;
				else
					break;
			}
			for(int k=test[i].l;k<=100;k++)
			{
				if(vis[k])
				{
					vis[k]--;
					num++;
					ans+=(test[i].time*500+test[i].l*2);
					break;           //只要找到第一个break 后面无需再找
				}
			}
		}
		cout<<num<<" "<<ans<<endl;
	}
	return 0;
}

HDU 3090

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

给出n条路和m的钱数 每条路上有固定的长度和强盗数目 每条路上的强盗会抢走强盗数量*道路长度的钱 一个硬币可以避免1km不受强盗影响
问至少有多少钱会被抢走

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
	int d,p;
}road[10050];
int cmp(node x,node y)    //按照强盗数量排序 多的在前面
{
	if(x.p==y.p)
		return x.d>y.d;
	return x.p>y.p;
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int n,m;
	while(cin>>n>>m)
	{
		if(n==0&&m==0)
			break;
		int sum=0;
		for(int i=1;i<=n;i++)
		{
			cin>>road[i].d>>road[i].p;
			sum+=road[i].d*road[i].p;   //先算出总的要抢钱数
		}
		sort(road+1,road+1+n,cmp);
		for(int i=1;i<=n;i++)
		{
			if(m>=road[i].d)    //能解决掉的部分 对应的钱数也要减掉
			{
				m-=road[i].d;
				sum-=road[i].d*road[i].p;
			}
			else      //解决不了某段路 减去最后能解决的部分 结束循环
			{         //剩下的sum都是要抢的钱数了
				sum-=m*road[i].p;
				break;
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}

本文标题:贪心杂选

文章作者:Hippopmonkey

发布时间:2017-02-07, 21:23:13

最后更新:2017-02-08, 15:26:18

原始链接:http://xuboming8.github.io/2017/02/07/贪心杂选/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 贪心杂选
    1. 1.1. HDU 4296
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
    2. 1.2. HDU 4310
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
    3. 1.3. HDU 5661
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
    4. 1.4. HDU 1789
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
    5. 1.5. HDU 4864
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
    6. 1.6. HDU 3090
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
|