2020-06-29

• 买了枕头。（希望早点到）
• 两顿都在食堂吃。
• 我给迷惑行为打赏投稿的沙雕被采纳了。
• 晚上有出去夜跑。

Codeforces Round #653 (Div. 3)

E2 - Reading Books (hard version)

和我昨天E1的思路类似。（题意在昨天）

还是要分成四类，主要枚举两者都喜欢的书选用的个数p3。

那么那些被单独喜欢的书至少要选k-p3本。

剩下如果还不足m本书，我们就在没人喜欢，和单独喜欢的书中贪心挑。

稍微用一点编程技巧优化，复杂度不会很大。

我被.size()卡住了。注意一般size_t类型都是被编译器解释成无符号类型的。如果参与逻辑运算，会把所有的数值都转化成无符号类型运算。这样就让负数会产生意外。

/**
  *    █████╗  ██████╗       ██████╗ ██╗     ███████╗
  *   ██╔══██╗██╔════╝       ██╔══██╗██║     ╚══███╔╝
  *   ███████║██║            ██████╔╝██║       ███╔╝
  *   ██╔══██║██║            ██╔═══╝ ██║      ███╔╝
  *   ██║  ██║╚██████╗▄█╗    ██║     ███████╗███████╗
  *   ╚═╝  ╚═╝ ╚═════╝╚═╝    ╚═╝     ╚══════╝╚══════╝
  *
  *  @Author: TieWay59
  *  @Created: 2020/6/29 15:46
  *  @Link: https://codeforces.com/contest/1374/problem/E2
  *  @Tags:
  *
  *******************************************************/

#include <bits/stdc++.h>

#ifdef DEBUG

#   include "libs59/debugers.h"
//  #define debug(x)  cerr <<#x << " = "<<x<<endl;
#else
#   define endl '\n'
#   define debug(...)
#   define max(x,y) ((x)>(y)?(x):(y))
#   define min(x,y) ((x)>(y)?(y):(x))
#endif

#define STOPSYNC ios::sync_with_stdio(false);cin.tie(nullptr)
#define MULTIKASE int Kase=0;cin>>Kase;for(int kase=1;kase<=Kase;kase++)
#define SIZE(x)  int((x).size())
typedef long long ll;
const int MAXN = 2e5 + 59;
const int MOD = 1e9 + 7;
const int INF = 0x3F3F3F3F;
const ll llINF = 0x3F3F3F3F3F3F3F3F;
using namespace std;
using pii = pair<ll, ll>;
using vint = vector<int>;


void solve(int kaseId = -1) {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<pii>> a(4);

    for (int i = 1; i <= n; ++i) {
        ll ti, ai, bi;
        cin >> ti >> ai >> bi;
        a[ai << 1 | bi].emplace_back(ti, i);
    }

    for (auto &ai : a) {
        sort(ai.begin(), ai.end());
    }

    auto sum(a);

    for (auto &ai : sum) {
        int pre = 0;
        for (auto &aij : ai) {
            aij.first += pre;
            pre = aij.first;
        }
    }


    int p0 = 0;
    int p1 = 0;
    int p2 = 0;
    ll ans_val = llINF;
    vint ans_ps;

    auto get_time = [&a](const int &tp, const int &ps) -> ll {
        if (ps >= SIZE(a[tp])) return llINF;
        return a[tp][ps].first;
    };

    for (int p3 = min(m, (int) a[3].size()); p3 >= 0; --p3) {
        if (k - p3 > min(SIZE(a[1]), SIZE(a[2]))) continue;
        if (m - p3 > SIZE(a[0]) + SIZE(a[1]) + SIZE(a[2])) continue;
        if (m - p3 < (k - p3) * 2) continue;

        ll t = p3 > 0 ? sum[3][p3 - 1].first : 0ll;

        p2 = max(p2, k - p3);
        p1 = max(p1, k - p3);
        p0 = min(p0, m - p3 - p2 - p1);

        while (p3 + p2 + p1 + p0 < m) {
            ll x2 = get_time(2, p2);
            ll x1 = get_time(1, p1);
            ll x0 = get_time(0, p0);
            if (x0 <= min(x1, x2)) p0++;
            else if (x1 <= min(x0, x2)) p1++;
            else p2++;
        }

        if (p2) t += sum[2][p2 - 1].first;
        if (p1) t += sum[1][p1 - 1].first;
        if (p0) t += sum[0][p0 - 1].first;

        if (t < ans_val) {
            ans_val = t;
            ans_ps = {p0, p1, p2, p3};
            debug(ans_ps);
        }
    }

    if (ans_val == llINF) {
        cout << -1 << endl;
    } else {
        cout << ans_val << endl;
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < ans_ps[i]; ++j) {
                cout << a[i][j].second << " ";
            }
        }
        cout << endl;
    }
}

void solves() {
    MULTIKASE {
        solve(kase);
    }
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r+", stdin);
#endif
    STOPSYNC;

    solve();
    return 0;
}
/*

 */

F没意思了，明天整理一下蓝桥。

2020-06-30

• 整理一下蓝桥杯的东西。
• 牛客剑指offer
• 字节跳动？（问问学姐（哇太难了，有点做梦。
• 数据学院？（没通知（来了来了。
• snowkylin.github.io 雪老师也太优秀了，我顶礼膜拜。
• 明天要去打扫卫生。回归机房生活啦。
• 就写了两题，晚上还跑步了，明天再说。

2020-07-01

• 大清早去机房打扫卫生，发现很多人都要离开了。
• 买了力扣的30天会员，玩玩看。
• 刷了好多困难题，其实还不算太难。
• 打了div2，但是感觉好像不是很会= =。（想学一下E和F）
• 晚上跑步了，还修好了机房的网络，挺好的。
• 明天九点多去机房贴二维码。
• 明天八点强717优惠券。
• 一天就这么过去了，明天再接再厉。

What does not kill me makes me stronger

From Wikipedia, the free encyclopedia

Jump to navigationJump to search

What does not kill me makes me stronger (German Was mich nicht umbringt macht mich stärker) is part of aphorism number 8 from the “Maxims and Arrows” section of Friedrich Nietzsche’s Twilight of the Idols (1888). In full, it is:

Aus der Kriegsschule des Lebens. — Was mich nicht umbringt, macht mich stärker.
Out of life’s school of war — What does not kill me makes me stronger.

It is quoted or alluded to by many other works, with minor variants in wording

wiki

专业见习动员大会

我总结一下开会的内容：

• 专业实习课程推掉的还是要选上，学号姓名报给我，我帮大家申请回来。
• 延期的同学分数会迟点补录，不影响。
• 延期申请表有空就写起来交给教务办（应该是找周莹老师），最迟开学第一周交过去。
• 实习时间要求在9月多开始，我们要至少10周（注意填写材料）。
• 平台在校友帮，大多数材料都在校友帮上可以下载。
• 实在找不到实习，早点去教务办跟老师交流一下。
• 他们要求实习岗位要和专业相关，因为你的材料会给专业主任审核的，他觉得不行可能会申请不通过。

2020-07-02

• 早上去机房贴了二维码（有四个位置我贴反了）
• leetcode做了两道题。
• 去取了快递，有新枕头了，开心。（辰巨听信了一套梳子护发的理论，我也开始相信了。）
• 今天好多阵雨暴雨，出去很不爽。
• 晚上在看

  除特别声明，本站所有文章均为原创，如需转载请以超级链接形式注明出处：SmartCat's Blog