C-晾衣服

链接：https://ac.nowcoder.com/acm/contest/892/C

题意：

鸡尾酒从杭州回来，囤积了许多衣服，洗好之后，他发现晾衣服是一件麻烦的事。

晾衣绳的长度只有L，而鸡尾酒有N件衣服，每件衣服挂在衣架上之后可以横着晾或者竖着晾，横着晾比较占晾衣绳的地方，但是受光面积大，干得也快，竖着晾反之。

鸡尾酒每天都要专心卖萌，没时间管这些衣服，所以在挂好每件衣服之后就不会再调整，他只希望能最快的看到所有衣服全部被晾干。

请你帮鸡尾酒算算，假如他以最优决策挂衣服，最早经过多长时间，所有衣服都能被晾干。

如果他永远无法一次性晾干所有衣服，输出-1。

思路：

贪心没贪出来，赛后看是二分。

直接二分答案。

统计长度要用到longlong

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 2e5+10;

const int INF = 1e9;

struct Node

{

    int time, hlen, ht, slen, st;

    int nht, nst;

    void Init()

    {

        nht = (time+ht-1)/ht;

        nst = (time+st-1)/st;

    }

}node[MAXN];

int n, sum;

bool Check(int time)

{

    LL need = 0;

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

    {

        if (node[i].nst <= time && node[i].nht <= time)

            need += min(node[i].slen, node[i].hlen);

        else if (node[i].nst <= time)

            need += node[i].slen;

        else if (node[i].nht <= time)

            need += node[i].hlen;

        else

            return false;

    }

    if (need <= sum)

        return true;

    return false;

}

int main()

{

    scanf("%d%d", &n, &sum);

    LL lesslen = 0;

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

    {

        scanf("%d%d%d%d%d", &node[i].time, &node[i].hlen, &node[i].ht, &node[i].slen, &node[i].st);

        lesslen += min(node[i].slen, node[i].hlen);

        node[i].Init();

    }

    if (lesslen > sum)

    {

        cout << -1 << endl;

        return 0;

    }

    int l = 1, r = 1e9;

    int res;

    while (l <= r)

    {

        int mid = (l+r)/2;

        if (Check(mid))

        {

            res = mid;

            r = mid-1;

        }

        else

        {

            l = mid+1;

        }

    }

    cout << res << endl;

    return 0;

}

巴特西

C-晾衣服

链接：https://ac.nowcoder.com/acm/contest/892/C

题意：

思路：

代码：

最新文章

热门文章