题目大意:两个城市A,B分别有两个护盾,现已知B护盾开启的时间和持续的时间,两个城市互相射击炮弹,如果打到的城市有护盾则反弹给另一个。现在问你要使得A城市最小受到的伤害是多少?
算法思路:我们只需要算出每颗炮弹给A造成的伤害区间,将其转化为区间交问题,即可。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define MAXN 50050 typedef long long LL; LL ta,tb,stb,st,ct,dam; int na,nb; typedef struct Shield { LL l,r; LL dam; }; Shield s[MAXN]; bool cmp(Shield s1,Shield s2) { return s1.r<s2.r; } LL k[MAXN],f[MAXN]; void add(int w,LL value) { for(;w<=MAXN;w+=w&-w) f[w]+=value; } LL getSum(int w) { LL value=0; for(;w;w-=w&-w) value+=f[w]; return value; } int main() { LL lb,rb,la,ra,sum,MAX; int ssnum,ssnum2; while(scanf("%lld%lld",&ta,&tb)!=EOF) { sum=0; ssnum=0,ssnum2=0; scanf("%lld",&stb); lb=stb,rb=stb+tb; scanf("%d%d",&na,&nb); //a炮弹 for(int i=1;i<=na;i++) { scanf("%lld%lld%lld",&st,&ct,&dam); if (st+ct<lb||st+ct>rb) continue ; else { ssnum++; s[ssnum].l=st+2*ct; s[ssnum].dam=dam; sum+=dam; s[ssnum].r=st+2*ct+(rb-st-ct)/(2*ct)*(2*ct); } } //b炮弹 for(int i=1;i<=nb;i++) { scanf("%lld%lld%lld",&st,&ct,&dam); ssnum++; s[ssnum].l=st+ct; s[ssnum].dam=dam; sum+=dam; if (rb<st+2*ct||st+2*ct<lb) s[ssnum].r=s[ssnum].l; else s[ssnum].r=st+3*ct+(rb-st-2*ct)/(2*ct)*(2*ct); } for(int i=1;i<=ssnum;i++) { k[++ssnum2]=s[i].l; k[++ssnum2]=s[i].r; k[++ssnum2]=s[i].r-ta; } sort(s+1,s+ssnum+1,cmp); sort(k+1,k+ssnum2+1); int K=unique(k+1,k+ssnum2+1)-(k+1);//去重 memset(f,0,sizeof(f)); MAX=0; for(int i=1;i<=ssnum;i++) { int k1=lower_bound(k+1,k+K+1,s[i].l)-k; int k2=lower_bound(k+1,k+K+1,s[i].r)-k; int k3=lower_bound(k+1,k+K+1,s[i].r-ta)-k; add(k1,s[i].dam); MAX=max(MAX,getSum(k2)-getSum(k3-1)); } printf("%lld\n",sum-MAX); } return 0; }
相关推荐
Countires网站 通过输入国家名称获取国家标志,本地名称和国际名称的网站 目录 基本信息 这个项目是简单的网站,其中包含: 带有简单验证的登录页面,用户名和密码only 5 characters 搜索输入已验证的主页, only-...
Countires Web App可在台式机,平板电脑和移动设备上使用。 该应用程序可用于多种目的,包括提供教育以支持项目事实或供潜在旅行者研究目的地。 该应用程序包含一个简单的下拉框,用户可以在其中选择所需的国家/...
注意:您必须先添加countires 表,因为所有其他表都依赖于它,否则您应该更改SQL 文件以删除依赖项。 国家 如果你想添加countires,请先添加{db}/countries/countries.sql文件。 然后你也可以添加 i18n 来获取不同...
本文的目的是为开放式创新平台提出一种新的商业模式,该平台特别适合发展中国家的移动电话部门。 在许多情况下,开放式创新已被证明是进行创新的一种优越手段,但是迄今为止,在发展中国家,开放式创新仅得到了很少...
基于java的贝儿米幼儿教育管理系统答辩PPT.pptx
本压缩包资源说明,你现在往下拉可以看到压缩包内容目录 我是批量上传的基于SpringBoot+Vue的项目,所以描述都一样;有源码有数据库脚本,系统都是测试过可运行的,看文件名即可区分项目~ |Java|SpringBoot|Vue|前后端分离| 开发语言:Java 框架:SpringBoot,Vue JDK版本:JDK1.8 数据库:MySQL 5.7+(推荐5.7,8.0也可以) 数据库工具:Navicat 开发软件: idea/eclipse(推荐idea) Maven包:Maven3.3.9+ 系统环境:Windows/Mac
基于java的消防物资存储系统答辩PPT.pptx
项目经过测试均可完美运行! 环境说明: 开发语言:java jdk:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse
项目经过测试均可完美运行! 环境说明: 开发语言:java jdk:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse
TA_lib库(whl轮子),直接pip install安装即可,下载即用,非常方便,各个python版本对应的都有。 使用方法: 1、下载下来解压; 2、确保有python环境,命令行进入终端,cd到whl存放的目录,直接输入pip install TA_lib-xxxx.whl就可以安装,等待安装成功,即可使用! 优点:无需C++环境编译,下载即用,方便
使用软件自带的basic脚本编辑制作的脚本 低版本软件无法输出Excel报告,可以通过脚本方式实现这一功能
基于java的就业信息管理系统答辩PPT.pptx
25法理学背诵逻辑.apk.1g
基于java的大学生校园兼职系统答辩PPT.pptx
做到代码,和分析的源数据
本压缩包资源说明,你现在往下拉可以看到压缩包内容目录 我是批量上传的基于SpringBoot+Vue的项目,所以描述都一样;有源码有数据库脚本,系统都是测试过可运行的,看文件名即可区分项目~ |Java|SpringBoot|Vue|前后端分离| 开发语言:Java 框架:SpringBoot,Vue JDK版本:JDK1.8 数据库:MySQL 5.7+(推荐5.7,8.0也可以) 数据库工具:Navicat 开发软件: idea/eclipse(推荐idea) Maven包:Maven3.3.9+ 系统环境:Windows/Mac
项目经过测试均可完美运行! 环境说明: 开发语言:java jdk:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse
适用于ensp已经入门人群的学习,有一定难度
基于java的数码论坛系统设计与实现答辩PPT.pptx
tornado-6.4.1-cp38-abi3-macosx_10_9_universal2.whl