Magic Potions

Stella981
• 阅读 679

题目描述:

一堆东西,每次拿出两个不同的东西合。要最终合出来的最多。并且要贪心的买12 13 14.。。1n 23.。。
http://codeforces.com/gym/100430/attachments/download/2418/20092010-summer-petrozavodsk-camp-andrew-stankevich-contest-36-asc-36-en.pdf

题解:

首先要保证总个数是最多的。怎么算总个数?求一下maxelement,然后sum-maxelement和max值比较,大中小对应情况。
其次要贪心的去取,那么我们最直接的:取12 取13.。。。可以取就一直取,如果取完算一下剩下的东西不能凑成原来的最优的结果的话,那么二分找到最大能够取得那个值。把它给取了。之后一旦发生这样的情况,说明已经到了后面的东西全部都和后面的最高值合并的特殊情况(这一点很重要),我们直接killit就好了。

另外也有一种其他方法:先贪心的合并,然后可能剩余一个有很多数量,再倒着拆已经合好的石头和这个剩余的合并。

重点:

(1)会算最大个数。
(2)按照题目中贪心。不能取的时候发现已经到了特殊情况。
(3)注意max=6 sum-max=7的情况。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <ctype.h>
#include <limits.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
#include <assert.h>
#define CLR(a) memset(a, 0, sizeof(a))
#define REP(i, a, b) for(ll i = a;i < b;i++)
typedef long long ll;

using namespace std;

const ll maxn = 1e5 + 100;
struct info
{
    ll a, b, num;
    info(ll _a = 0, ll _b = 0, ll _num = 0)
    {
        a = _a;
        b = _b;
        num = _num;
    }
    bool operator < (const info & other) const
    {
        if(a == other.a)
        {
            return b < other.b;
        }
        return a < other.a;
    }
};

ll maxA[maxn], sum, maxa, maxi;
ll a[maxn];
ll n;
ll tot;
vector<info> ans;
vector<info> ansPro;
void killIt(ll key)
{
    for(ll i =1; i<=n; i++)
    {
        if(i != key && a[i] > 0 && a[key]>0)
        {
            ll sub = min(a[i], a[key]);
            if(sub > 0)
            {
   
   
   
                ans.push_back(info(min(i, key), max(i, key), sub));
                a[i]-=sub;
                a[key] -= sub;
            }
        }
    }
}

void outPut()
{
    sort(ans.begin(), ans.end());
//    ll resSum = 0;
//    ansPro.clear();
//    for(ll i = 0; i<ans.size(); i++)
//    {
//        if(ans[i].num != 0)
//        {
//            ansPro.push_back(ans[i]);
//        }
//    }
//    ans.clear();
//    sort(ansPro.begin(), ansPro.end());
//    for(ll i = 0; i<ansPro.size(); i++)
//    {
//        resSum += ansPro[i].num;
//        if(i!=0)
//        {
//            if(ansPro[i].a == ans[ans.size()-1].a && ansPro[i].b == ans[ans.size()-1].b)
//            {
//                ans[ans.size()-1].num += ansPro[i].num;
//            }
//            else
//            {
//                ans.push_back(ansPro[i]);
//            }
//        }
//        else
//        {
//            ans.push_back(ansPro[i]);
//        }
//    }
    //ll tsum = 0;
    ll tempAns = ans.size();
    printf("%I64d\n", tempAns);
    for(ll i = 0; i<ans.size(); i++)
    {
        //tsum += ans[i].num;
        printf("%I64d %I64d %I64d\n", ans[i].a, ans[i].b, ans[i].num);
    }
    //printf("%d -----\n", tsum);
}
ll gettot(ll mm, ll sum)
{
    if(mm <= sum-mm)
        return sum/2;
    return sum-mm;
}
ll solve(ll &now1, ll &now2)
{
   ll sub = min(a[now1], a[now2]);
   ll tmpMax = max(a[now1],a[now2])-sub;
   ll tmpSum = sum - sub*2;
   tmpMax = max(maxA[now2+1], tmpMax);
   ll tmptot = gettot(tmpMax, tmpSum);

   if(tmptot+sub==tot)
   {
   
   
   
       sum = tmpSum;
       a[now1]-=sub;
       a[now2]-=sub;
       tot -= sub;
       ans.push_back(info(now1, now2, sub));
       if(a[now2]==0&&a[now1]==0)
       {
           now1=now2+1;
           now2=now1+1;
       }
       else if(a[now2]==0)
       {
           now2++;
       }
       else
       {
           now1 = now2;
           now2++;
       }
       return 1;
   }
   else
   {
       ll l = 0, r = sub;
       while(l < r)
       {
           ll mid = (l+r)/2;
           tmpSum = sum-2*mid;
           tmpMax = max(a[now1],a[now2])-mid;
           tmpMax = max(tmpMax, maxA[now2+1]);
           tmptot = gettot(tmpMax, tmpSum);
           if(tmptot+mid==tot)
           {
               l = mid+1;
           }
           else
           {
               r = mid;
           }
       }
       r--;
       if(r!=0)
        ans.push_back(info(now1, now2, r));
       ll maxI = now1, maxA = a[now1]-r;
       sum -= 2*r;
       a[now1] -= r;
       a[now2] -= r;
       for(ll i = now2;i<=n;i++)
       {
           if(a[i]>maxA)
           {
               maxA = a[i];
               maxI = i;
           }
       }
       killIt(maxI);
       return 0;
   }
}
void gao()
{
    sum = 0;
    for(ll i = 1; i<=n; i++)
    {
        sum += a[i];
    }
    maxi = max_element(a+1, a+1+n)-a;
    maxa = a[maxi];
    a[n+1] = 0;
    maxA[n+1]=0;
    for(ll i = n;i>=1;i--)
    {
        maxA[i]=max(maxA[i+1], a[i]);
    }
    ans.clear();
    if(!(maxa>=sum-maxa))
    {
        tot = sum/2;
        ll l = 1, r = 2;
        while(r<=n)
        {
            ll flag = solve(l, r);
            if(flag==0)
                break;
        }
    }
    else
    {
        killIt(maxi);
    }
    outPut();
}

int main()
{
    //freopen("11Kin.txt", "r", stdin);
    //freopen("1out.txt", "w", stdout);
    freopen("magic.in", "r", stdin);
    freopen("magic.out", "w", stdout);
    while(scanf("%I64d", &n)!=EOF)
    {
        for(ll i =1; i<=n; i++)
        {
            scanf("%I64d", &a[i]);
        }
        gao();
    }
    return 0;
}

本文分享 CSDN - ruclion。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这