首页 > ACM题库 > HDU-杭电 > hdu 2542 补兵-线段树-[解题报告]C++
2014
02-10

hdu 2542 补兵-线段树-[解题报告]C++

补兵

问题描述 :

在非常流行的DOTA游戏中,补兵是非常重要的一种技术统计。如果一个单位被对方的多个单位攻击至死,则对该单位造成最后一次(致命的)伤害的攻击者将会获得更多的奖励(金钱和经验),这名攻击者被记录一次补兵。
现在假设有多个人攻击对方的一个单位,而你是其中的一个,你并不想在前面出手攻击,而只想打一次就直接将对方打死,完成一次补兵。假设其他人每次攻击的伤害和每两次攻击之间的间隔都是固定的,而你的攻击伤害也是固定的。输入将给出每个人两次攻击之间的间隔时间,并假设每个人第一次攻击的时刻值就是他的两次攻击之间的时间间隔值。例如,一个人攻击间隔为2,则他会在时刻2、4、6、8……进行攻击。
时间以整数计算。
如果多个人同时攻击导致对方死亡,攻击伤害最大的那个被记录一次补兵。如果你是攻击伤害最大的之一(还有其他和你攻击伤害一样的,但没有更大的),则你被记录一次补兵。
一个单位血量小于等于0就被判为死亡。
你的任务是求出合适的攻击时间段,使得这次补兵能够完成。这个时间段一定是一个区间,你需要输出的是它的两个端点。

输入:

输入包含多组数据。每组数据第一行是一个整数N(2<=N<=1000),表示攻击对方某个单位的人数。N=0表示输入结束。接下来有N-1行,每行两个整数,分别表示每个人每次攻击的伤害A(1<=A<=10),以及每两次攻击之间的间隔T(1<=T<=100)。最后有一行包含两个整数,分别表示你的攻击伤害P(1<=P<=100000)以及对方单位的血量H(P<H<=1000000)。

输出:

输入包含多组数据。每组数据第一行是一个整数N(2<=N<=1000),表示攻击对方某个单位的人数。N=0表示输入结束。接下来有N-1行,每行两个整数,分别表示每个人每次攻击的伤害A(1<=A<=10),以及每两次攻击之间的间隔T(1<=T<=100)。最后有一行包含两个整数,分别表示你的攻击伤害P(1<=P<=100000)以及对方单位的血量H(P<H<=1000000)。

样例输入:

2
2 2
3
10
2
20 2
3
10
0

样例输出:

8 10
Impossible

提示:
输入数据较多,尽量用scanf和printf代替cin和cout

#include<stdio.h>
int k;
struct stu
{
    int x;
    int mx;
}bu[110];
int f(int j)
{
    int i,m=0,mxx=0;
     for(i=1;i<=100;i++)
              if(bu[i].mx)
                m=m+(j/i)*bu[i].x;
       return m;
}
int main()
{
    int i,j,x,t,m,n,P,H,l,mxx;
    double s,x1,t1,n1,y1;
    while(scanf("%d",&n)&&n)
    {
        for(i=0;i<=100;i++)
            bu[i].mx=bu[i].x=0;
            s=0;
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&x,&t);
            bu[t].x=bu[t].x+x;
            if(x>bu[t].mx)bu[t].mx=x;
            x1=x;
            t1=t;
            s=s+x1/t1;
        }
        scanf("%d%d",&P,&H);
        x1=H;
        y1=P;
        n1=(x1-y1)/s;
        n=n1;
        if(n==0)n=1;
        l=0;
        for (i=n;i<=100+n;i++)
        {     m=0;mxx=0;
           for(j=1;j<=100;j++)
           {
              if(bu[j].mx)
              {
                 m=m+(i/j)*bu[j].x;
                 if(i%j==0&&bu[j].mx>mxx)
                 mxx=bu[j].x;
              }
           }
           if(m+P>=H&&mxx<=P){l=i;break;}
           else if(m+P>=H)
           break;
        }
        if(l==0)
        {
            printf("Impossible\n");
            continue;
        }
        printf("%d",l);
        n1=x1/s;
        n=n1;
        for(j=n+100;j>=l;j--)
        {
            m=0; mxx=0;
             for(i=1;i<=100;i++)
          {
              if(bu[i].mx)
             {
                m=m+(j/i)*bu[i].x;
                if(j%i==0&&bu[i].mx>mxx)
                mxx=bu[i].mx;
             }
           }
           if(m+P>=H&&mxx<=P&&f(j-1)<H){printf(" %d\n",j);break;}
        }
    }
    return 0;
}

  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }