消灭兔子

2024-02-06 19:32
文章标签 兔子 消灭

本文主要是介绍消灭兔子,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

消灭兔子
Problem : 1009
Time Limit : 1000ms
Memory Limit : 65536K
description
有N只兔子,每只有一个血量B[i],需要用箭杀死免子。有M种不同类型的箭可以选择,每种箭对兔子的伤害值分别为D[i],价格为P[i](1 <= i <= M)。假设每种箭只能使用一次,每只免子也只能被射一次,计算要消灭地图上的所有兔子最少需要多少Q币。如不能杀死所有兔子,请输出No Solution。
特别说明:1、当箭的伤害值大于等于兔子的血量时,能将兔子杀死;2、血量B[i],箭的伤害值D[i],箭的价格P[i],均小于等于100000。
input
第1行:两个整数N,M,中间用空格分隔(1 <= N, M <= 50000),分别表示兔子的个数和箭的种类。
第2 - N + 1行:每行1个正整数(共N行),表示兔子的血量B[i](1 <= B[i] <= 100000)。
第N + 2 - N + M + 1行:每行2个正整数(共M行),中间用空格分隔,表示箭所能造成的伤害值D[i],和需要花费的Q币P[i](1 <= D[i], P[i] <= 100000)。
output
输出最少需要多少Q币才能消灭所有的兔子。如果不能杀死所有兔子,请输出”No Solution”。
sample_input
3 3
1
2
3
2 1
3 2
4 3
sample_output
6
hint
source
51nod点头网

这题目分析是贪心,但是我一开始想着按照箭的价值从小到大排序了,然后将血量从小到大排序,然后从价值小到大枚举所有箭,(二分答案(未用)),就是尽量让箭的伤害刚好大于兔子的血量,但是这样如何判断全部兔子杀死了,如果每次轮询,结果超时。

//TLE:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int b[60000],flag[60000];struct jian
{int x;int y;
}a[60000];int cmp(const jian &a,const jian &b)
{if(a.y==b.y)return a.x<b.x;elsereturn a.y<b.y;
}int main()
{int n,m;while(scanf("%d%d",&n,&m)==2){memset(flag,0,sizeof(flag));for(int i=0;i<n;i++)scanf("%d",&b[i]);for(int i=0;i<m;i++)scanf("%d%d",&a[i].x,&a[i].y);sort(a,a+m,cmp);sort(b,b+n);if(n>m)printf("No Solution\n");else{int sum=0;for(int i=0;i<m;i++){for(int j=n-1;j>=0;j--)if(flag[j]==0&&a[i].x>=b[j]){sum+=a[i].y;flag[j]=1;break;}}int fl=0;for(int j=0;j<n;j++){fl+=flag[j];}if(fl>=n)printf("%d\n",sum);elseprintf("No Solution\n");}}
}

`
后来看标程将所有兔子血量从大到小,以及伤害从大到小排序,这样对于每一只兔子可能有几只能够杀死他的箭,选择价值最小的那一个将他杀死即可,然后用当前能够杀死第二只兔子的所有箭中价值最小的去杀死第二只。。。。直到有一只兔子没有箭能够杀死他,或者把所有兔子全部杀死。这里要用到优先队列。
就是枚举所有兔子,将大于第一只兔子的所有箭入队列,并且按照价值从小到大,然后取出最小的杀死第一只,然后将箭伤害大于第二只兔子的所有箭入队列,当然队列里面还有能够杀死第一只兔子的箭,然后选择最小价值杀死第二只,直到队列空或者全部杀死,这样处理起来要比我那种方案方便多了。

#include <iostream>  
#include <cstdlib>  
#include <cstring>  
#include <algorithm>  
#include <queue>  
using namespace std;  const int MAXN = 50001;  
int B[MAXN];  
int N,M;  
typedef struct DP  
{  int di;  int pi;  friend bool operator<(DP p1,DP p2)  {  return p1.pi > p2.pi;  }  
}Dp;  
Dp dp[MAXN];  
priority_queue<Dp>q;  bool cmpM(const Dp &a, const Dp &b)  
{  return a.di > b.di;  
}  bool cmpN(const int &a, const int &b)  
{  return a > b;  
}  int main()  
{  while (cin >> N >> M)  {  for (int i = 0; i < N; ++ i)  {  cin >> B[i];  }  sort(B,B+N,cmpN);  for (int i = 0; i < M; ++ i)  {  cin >> dp[i].di >> dp[i].pi;  }  sort(dp,dp+M,cmpM);  if (N>M)  {  cout << "No Solution"<< endl;  return 0;  }  __int64 sum = 0;  int cnt = 0;  bool flag = true;  int j = 0;  for (int i = 0; i < N; ++ i)  {  while (j < M && dp[j].di >= B[i])  {  q.push(dp[j]);  j ++;  }  if (q.empty())  {  flag = false;  break;  }  sum += q.top().pi;  q.pop();  }  if (flag)  {  cout << sum << endl;  }  else  cout << "No Solution"<< endl;  }  return 0;  
}  

这篇关于消灭兔子的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/685324

相关文章

兔子--Notification的使用

<span style="font-size:18px;color:#ff0000;"></span> <span style="font-size:18px;color:#ff0000;">使用步骤:</span><p><span style="font-size:18px;color:#ff0000;">1 获取通知管理器NotificationManager,它也是一个系统服务</sp

兔子--PendingIntent与Intent的区别

pendingIntent是一种特殊的Intent。 主要的区别在于Intent的执行立刻的,而pendingIntent的执行不是立刻的。 pendingIntent执行的操作实质上是参数传进来的Intent的操作, 但是使用pendingIntent的目的在于它所包含的Intent的操作的执行是需要满足某些条件的。 主要的使用的地方和例子:通知Notificatio

兔子--The method setLatestEventInfo(Context, CharSequence, CharSequence, PendingIntent) from the type

notification.setLatestEventInfo(context, title, message, pendingIntent);     不建议使用 低于API Level 11版本,也就是Android 2.3.3以下的系统中,setLatestEventInfo()函数是唯一的实现方法。  Intent  intent = new Intent(

兔子--背景透明度设置

背景透明度设置:ee是透明度 android:background="#ee6c6c6c"

兔子--Android Support v4,Android Support v7,Android Support v13

Android Support Library package用于高版本的特性的向下兼容。 (fragement,ViewPager) Android Support v4:  这个包是为了照顾1.6及更高版本而设计的,这个包是使用最广泛的,eclipse新建工程时,都默认 带有了。 Android Support v7:  这个包是为了考虑照顾2.1及以上版本而设计的,

兔子--Android Support v4包丢失的解决办法

在开发中,Android Support v4包丢失的解决办法: Project->properties->Java Build Path->Libraries->Add External Jars 中加入sdk目录下的extras/android/support/v4/android-support-v4.jar (如果找不到,则需要用sdk manager下载andro

兔子--SDK,ADT,AVD,IDE,ADB

a:SDK(Software Development Kit):开发android应用所需要的开发工具的集合,包括库文件及工具。 b:ADT(Android Developer Tools):在Eclipse下开发工具的升级下载工具。adt只是一个eclipse的插件,里面可以设置 sdk路径. c:IDE:集成开发环境。IDE通常包括编程语言编辑器、自动建立工具、通常还包括调试

兔子--eclipse下载插件

eclipse菜单栏->help->adout ADT->Installation Details->找到要卸载的插件->选中->点击下方uninstall

兔子--eclipse设置编码格式

设置编码格式 a:设置eclipse的默认编码格式:window->preferences->Workspace->Text File Encoding b:设置单个项目的编码格式::右键项目——Properties——Resource——Text file encoding