题解 P2392 【kkksc03考前临时抱佛脚】

· · 题解

记得之前做到过这道题

小S新买了一个掌上游戏机，这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏，他买了很多5号电池，这些电池的生产商不同，质量也有差异，因而使用寿命也有所不同，有的能使用5个小时，有的可能就只能使用3个小时。显然如果他只有两个电池一个能用5小时一个能用3小时，那么他只能玩3个小时的游戏，有一个电池剩下的电量无法使用，但是如果他有更多的电池，就可以更加充分地利用它们，比如他有三个电池分别能用3、3、5小时，他可以先使用两节能用3个小时的电池，使用半个小时后再把其中一个换成能使用5个小时的电池，两个半小时后再把剩下的一节电池换成刚才换下的电池（那个电池还能用2.5个小时），这样总共就可以使用5.5个小时，没有一点浪费。 （noi.openjudge.cn 4.6贪心 2469）

没想到这个人不能分开做题目，开始一道就必须做完

先说一下上面这道题的想法

对于每一门学科，先求出题目需要的时间的最大值，再与其他时间和作比较

1、如果一根电池就比其他所有电池时间和都长，那么最短时间就是这最长的电池持续的时间

2、如果这根电池时间比其他总和短，那么最短时间就是所有持续时间总和/2（可以证明）

于是我看到这道题的时候就直接糊了（应该很多人都是这样）

#include<iostream>
using namespace std;
int main()
{
    int tot=0,k,i,j,s[5]={0},t[5]={0},m[5]={0};//t-时间总和，m-时间最大值 
    cin>>s[1]>>s[2]>>s[3]>>s[4];
    for(j=1;j<=4;j++)
    {
        for(i=1;i<=s[j];i++)
        {
            cin>>k;
            if(k>m[j])m[j]=k;
            t[j]+=k;
        }
        if(t[j] % 2 ==0)//这里我注意到没有小数解（其实这里暗示了不能拆开做题）所以考虑奇数偶数 
        {
            if(m[j]>=t[j]/2)tot+=m[j];//一道题就比其他时间和长（也就是大于总和的一半） 
            else tot+=t[j]/2;//小于总和的一半 
        }
        else//示例中2 3 4例结果为5，应该是4与2+3 
        {
            if(m[j]>=(t[j]+1)/2)tot+=m[j];
            else tot+=(t[j]+1)/2;
        }
    }
    cout<<tot<<endl;
}

只有40分

蒟蒻不会DP

只能暴力搜索，还好数据量不算太大

#include<iostream>
#include<algorithm>
using namespace std;
int l,r,minn,tot=0;
int s[5]={0};
int a[5][21]={0};
void doit(int x,int y){
    if(y>s[x])
    {
        minn=min(minn,max(l,r));
        return;
    }
    l+=a[x][y];
    doit(x,y+1);
    l-=a[x][y];
    r+=a[x][y];
    doit(x,y+1);
    r-=a[x][y];
}
int main()
{
    int i,j;
    cin>>s[1]>>s[2]>>s[3]>>s[4];
    for(i=1;i<=4;i++)
    {
        minn=114514;
        l=0;
        r=0;
        for(j=1;j<=s[i];j++)
        {
            cin>>a[i][j];
        }
        doit(i,1);
        tot+=minn;
    }
    cout<<tot<<endl;
}

没有什么好解释的（我不知道什么叫剪枝太菜了）