hdu4020简单想法题

题意:

给你一些人,这些人有很多广告,每个广告有自己的点击率和长度,每次有m组询问,问每个人点击率前K名的广告的总长度是多少.

思路:

数据很大,很容易超时,总的想法还是先sort按照人,其次是点击率,这样就可以o(m)的时间吧每个广告的点击率排名搞定,然后在按照排名sort一变,就能用O(m)的时间吧sum[1--k]的答案打表出来,然后用O(1)的时间输出q组询问的答案就行了,刚开始因为多写了一个memset(50w的);各种超时,结果去掉之后3000多ac的..

#include<stdio.h>

#include<string.h>

#include<algorithm>



using namespace std;

typedef struct

{

   int id ,pm ,cli;

   __int64 l;

}NODE;

NODE node[500000+100];

__int64 ans[500000+100];

bool camp1(NODE a ,NODE b)

{

   return a.id < b.id || a.id == b.id && a.cli > b.cli;

}

bool camp2(NODE a ,NODE b)

{

   return a.pm < b.pm;

}

int main ()

{

   int n ,m ,q ,i ,j ,t ,cas = 1;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d %d %d" ,&n ,&m ,&q);

      for(i = 1 ;i <= m ;i ++)

      scanf("%d %d %I64d" ,&node[i].id ,&node[i].cli ,&node[i].l);

      sort(node + 1 ,node + m + 1 ,camp1);

      int k = 1 ,maxn = 0;

      for(i = 1 ;i <= m ;)

      {

         int aa = 1;

         while(node[i].id == k)

         {

            node[i].pm = aa++;

            i++;

            if(i > m)break;

         }

         k ++;

         if(maxn < aa - 1) maxn = aa - 1;

      }

      sort(node + 1 ,node + m + 1 ,camp2);

      ans[0] = 0;

      node[1].pm = 1;

      for(i = 1 ;i <= m ;i ++)

      {

         if(node[i].pm != node[i - 1].pm)

         {

            ans[node[i].pm] = node[i].l + ans[node[i].pm -1];

         }

         else

         ans[node[i].pm] += node[i].l;

      }

      printf("Case #%d:\n" ,cas ++);

      for(i = 1 ;i <= q ;i ++)

      {

         int a;

         scanf("%d" ,&a);

         if(a > maxn) a = maxn;

         printf("%I64d\n" ,ans[a]);

      }

   }

   return 0;

}

巴特西

hdu4020简单想法题

最新文章

热门文章