HDU 6011：Lotus and Characters（贪心）

http://acm.hdu.edu.cn/showproblem.php?pid=6011

题意：共有n种字符，每种字符有一个val和一个cnt，代表这个字符的价值和数量。可以制造的总价值是：第一个字符的权值*1+第二个字符的权值*2+第三个字符的权值*3+……。问最大的总价值可以是多少。

思路：首先可以确定价值越大的是放在越后，因为后面的位权比较大。考虑到价值有负数，因为不确定负数是否要放上去，所以需要枚举这些负数。

首先输入的时候记录价值为负的个数negnum。将价值从小到大排序，然后枚举1~negnum+1，用一个beg记录当前枚举哪种字符，还有tol记录当前种类的字符用了多少次了。如果当前种类的字符数用完了，就要将beg+1了，这样一直枚举下去，取最优。至于枚举到negnum+1的原因，是因为还要算一个负数都不取的情况会不会更优。计算的话可以通过等差数列求和公式（一个一个枚举怕超时，实际上看别人没超时）。至于在比赛时候WA的原因，因为粗心。。忘了只有枚举到的种类是beg的时候才要减去tol，其他不用。（比赛的时候所有都减去了tol，血崩）。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #include <iostream>

 using namespace std;

 #define N 1010

 #define M 200010

 #define INF 0x3f3f3f3f

 typedef long long LL;

 struct node {

     int val, cnt;

 } p[];

 bool cmp(const node &a, const node &b) { return a.val < b.val; }

 LL cal(int val, int cnt, int now) { // 等差数列

     int n = cnt + now;

     LL ans = val * n + (n * (n - )) /  * val;

     ans -= val * now + (now * (now - )) /  * val;

     return ans;

 }

 int main() {

     int t;

     scanf("%d", &t);

     while(t--) {

         int n;

         scanf("%d", &n);

         int negnum = ;

         for(int i = ; i <= n; i++) {

             scanf("%d%d", &p[i].val, &p[i].cnt);

             if(p[i].val < ) negnum += p[i].cnt;

         }

         sort(p + , p +  + n, cmp);

         LL ans = , tmp = ; int now = ;

         int beg = , tol = ;

         for(int i = ; i <= negnum + ; i++) { // 因为要看所有正数的情况，所以需要+1

             now = ; tmp = ;

             for(int k = beg; k <= n; k++) {

                 if(k == beg) tmp += cal(p[k].val, p[k].cnt - tol, now);

                 else tmp += cal(p[k].val, p[k].cnt, now);

                 if(k == beg) now += p[k].cnt - tol;

                 else now += p[k].cnt;

             }

             if(ans < tmp) ans = tmp;

             tol++;

             if(tol == p[beg].cnt) { beg++; tol = ; }

         }

         printf("%I64d\n", ans);

     }

     return ;

 }

巴特西

HDU 6011：Lotus and Characters（贪心）

最新文章

热门文章