发布于 由itewqq

[二分][贪心][比赛] 百度之星2018初赛(B) 1004 p1m2

哭了，真的是蠢，好多人三个题都前500了，我3个题吊车尾，感觉代码能力亟待提升。。。

二分答案，每次判断的时候用cnt记录遍历整个数组，比mid大的就cnt+=ar[i]-mid;小的就cnt+=mid-ar[i];这样其实算的是一个下限，也就是比他小的数都只加到了mid而没有多加，因为这样可以使得比mid大的那些，通过他们-2转移来的+1更好的利用，这样的话如果cnt<=0，那说明至少[mid,R]里仍然又满足要求的，所以应该往右边继续扩展，因为我们要求的是最大值！这里错了n发，就是没有搞清楚mid应该是靠右的而不是靠左emmmmmm。然后就是一开始想多了，上限下限都考虑了，后来才意识到要求的是最大值，只要下限可以操作就可以一直往右扩张。最后判断是否-1就是再把数组这样过一遍看看是不是cnt<=0，如果是的话说明是可以操作的（其实我很好奇怎么不可行。。 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include

using namespace std;
typedef long long LL;
const int maxn=300000+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

int ar[maxn];

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int T,n,mx,mi;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        mx=0;
        mi=1e9;
        for (int i=0; i>1;
            for (int i=0; imid)
                {
                    cnt1-=(ar[i]-mid)>>1;
                }
                else if(ar[i]<=mid)
                {
                    cnt1+=mid-ar[i];
                }
            }
            if(cnt1<=0)
                l=mid;
            else
                r=mid-1;
        }
        cnt1=0;
        mid=(r+l+1)>>1;
        for (int i=0; imid)
            {
                cnt1-=(ar[i]-mid)>>1;

            }
            else if(ar[i]<=mid)
            {
                cnt1+=mid-ar[i];
            }
        }

        if(cnt1<=0)
            printf("%d\n",mid);
        else
            printf("-1\n");
    }
    return 0;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据。