题目链接：
http://www.lydsy.com/JudgeOnline/problem.php?id=3709
http://www.lydsy.com/JudgeOnline/problem.php?id=4619
题意：n 个怪，有初始血量，打了第 i 个怪先扣\(a_i\) 血再加\(b_i\) 血，血小于等于 0 就死了，两道题分别问能不能死输出方案和最少欠少血...
对于打完加血的怪，显然按照扣血从小往大去打，因为如果这样都不能打某个加血的怪别的顺序一定也打不了...
对于打完扣血的怪，显然按照加血从大往小去打，因为这样如果都不能打某个扣血的怪别的顺序显然更打不了... 因为血越来越少
3709
|
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 57 58 59 60 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 1000010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct zgz { int x,y,id; }a[N],b[N]; bool cmp1(const zgz &a,const zgz &b) {return a.x<b.x;} bool cmp2(const zgz &a,const zgz &b) {return a.y>b.y;} int n,topa,topb; ll ans,ret; void cal(int x,int y) { ret-=x; if(ret<=0) { printf("NIE\n"); exit(0); } ret+=y; } int main() { int i; n=read();ret=read(); for(i=1;i<=n;++i) { int tmpa=read(),tmpb=read(); if(tmpa<=tmpb) a[++topa].x=tmpa,a[topa].y=tmpb,a[topa].id=i; else b[++topb].x=tmpa,b[topb].y=tmpb,b[topb].id=i; } sort(a+1,a+topa+1,cmp1); sort(b+1,b+topb+1,cmp2); for(i=1;i<=topa;++i) cal(a[i].x,a[i].y); for(i=1;i<=topb;++i) cal(b[i].x,b[i].y); puts("TAK"); for(i=1;i<=topa;i++)printf("%d ",a[i].id); for(i=1;i<=topb;i++)printf("%d ",b[i].id); return 0; } |
4619
|
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 57 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 1000010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct zgz { int x,y; }a[N],b[N]; bool cmp1(zgz a,zgz b) {return a.x<b.x;} bool cmp2(zgz a,zgz b) {return a.y>b.y;} int n,topa,topb; ll ans,ret; void cal(int x,int y) { ret-=x; if(ret<0) { ans-=ret; ret=0; } ret+=y; } int main() { n=read(); for(int i=1;i<=n;i++) { int tmpa=read(),tmpb=read(); if(tmpa<=tmpb) a[++topa].x=tmpa,a[topa].y=tmpb; else b[++topb].x=tmpa,b[topb].y=tmpb; } sort(a+1,a+topa+1,cmp1); sort(b+1,b+topb+1,cmp2); for(int i=1;i<=topa;i++) cal(a[i].x,a[i].y); for(int i=1;i<=topb;i++) cal(b[i].x,b[i].y); printf("%lld\n",ans); return 0; } |
Comments | NOTHING