正解:贪心

解题报告:

首先肯定是先打回血>扣血的,因为要保证不死,所以只能打扣血量小于当前血量的怪,又懒得判断打那个不会死,就按照扣血量升序排序就好

然后对剩下的扣血>回血的,感觉就比较难处理顺序了?可以考虑显然最后如果活下来了剩余的血量是已知的,所以考虑倒推,于是就回血扣血功能互换,依然是只要全程血量>0就好,所以就一样地做就好

然后这题就做完辣!

然后我忘记开ll了成功见祖宗,,,太难受了我调了1h+怎么也找不出问题然后数据也看不了darkbzoj还被封了无法get数据,,,自己怎么拍怎么对,,,原地死亡TT

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#define gc getchar()
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
 
const int N=100000+10;
int n,cnt1,cnt2;
ll hp;
struct nod{int a,b,id;}node1[N],node2[N];
 
il int read()
{
    rc ch=gc;ri x=0;rb y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
    return y?x:-x;
}
il bool cmp(nod gd,nod gs){return gd.a<gs.a;}
il bool cmq(nod gd,nod gs){return gd.b>gs.b;}
 
int main()
{
//  freopen("3709.in","r",stdin);
//  freopen("3709.out","w",stdout);
    n=read();hp=read();
    rp(i,1,n){ri x=read(),y=read();if(x<=y)node1[++cnt1]=(nod){x,y,i};else node2[++cnt2]=(nod){x,y,i};}
    sort(node1+1,node1+1+cnt1,cmp);rp(i,1,cnt1)if(hp<=node1[i].a)return printf("NIE\n"),0;else hp=hp+node1[i].b-node1[i].a;
    sort(node2+1,node2+1+cnt2,cmq);rp(i,1,cnt2)if(hp<=node2[i].a)return printf("NIE\n"),0;else hp=hp+node2[i].b-node2[i].a;
    printf("TAK\n");rp(i,1,cnt1)printf("%d ",node1[i].id);rp(i,1,cnt2)printf("%d ",node2[i].id);
    return 0; 
}

放个代码QAQ

BZOJ3709 Bohater 贪心

正解:贪心

解题报告:

相关推荐