Codeforces Round #611 (Div. 3)

Stella981
• 阅读 636

原题面:https://codeforces.com/contest/1283

A.Minutes Before the New Year

题目大意:给定时间,问距离零点零分还有多久?

分析:注意一下特判0,0就好了。

代码:

t = input()
t = int(t)
for i in range(t):
    h, m = input().split()
    h = int(h)
    m = int(m)
    if h == 0 and m == 0:
        print(0)
        continue
    ret = 24 * 60
    ret -= h * 60
    ret -= m
    print(ret)

B.Candies Division

题目大意:分糖果,得到糖果数最多的人的糖果数与得到糖果数最少的人的数量之差不能大于一。并且得到糖果数量最多的人不得多于人数的一半。

分析:简单的数学题,比较一下得到糖果数最多与最少相等的情况和得到糖果数最多比最少多一的情况即可。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int t;
    ll n, k;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        ll average = n / k;
        ll remain = n - average * k;
        cout << average * k + min(remain, k / 2) << endl;
    }
    return 0;
}

C.Friends and Gifts

题目大意:每个人都要给其他一个人一个礼物,并且每个人都要收到一个礼物。请你构造一种合法的赠送礼物的方法,使得每个人都赠送非自己的人一个礼物,并且从其他人那里收到一个礼物。

分析:贪心的构造题?不知道啊,反正乱搞就过了。先把没收到礼物的找出来,再把没赠送礼物的找出来,题目保证这两类人数相等,再按合法的方法构造就行了。

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
int f[maxn],in[maxn],out[maxn];
vector<int> need_out;
vector<int> need_in;
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> f[i];
    for (int i = 1; i <= n; i++) {
        if (!f[i])
            out[i] = 0;
        else
            out[i]++, in[f[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (!in[i]) {
            need_in.push_back(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!out[i]) {
            need_out.push_back(i);
        }
    }
    sort(need_in.begin(), need_in.end(), less<int>());
    sort(need_out.begin(), need_out.end(), less<int>());
    bool flag = true;
    while (flag) {
        flag = false;
        int sz = need_in.size();
        for (int i = 0; i < sz; i++) {
            if (need_in[i] == need_out[i]) {
                flag = true;
                swap(need_out[need_out.size() - 1], need_out[i]);
            }
        }
        for (int i = sz - 1; i >= 0; i--) {
            if (need_in[i] == need_out[i]) {
                flag = true;
                swap(need_out[0], need_out[i]);
            }
        }
    }
    for (int i = 0; i < need_in.size(); i++) {
        f[need_out[i]] = need_in[i];
    }
    for (int i = 1; i <= n; i++) {
        cout << f[i] << (i == n ? '\n' : ' ');
    }
    return 0;
}

D.Christmas Trees

题目大意:给定n个不同的整数点,让你找m个不同的整数点,使得这m个点到到这n个点最小距离之和最小。

分析:对于每个点,肯定是先选取距离为1的,然后再选取距离为2的,以此类推。但是有的点不一定选得到,因此我们可以用队列来存储那些可以到达的点,这样就可以得知这个题跑个bfs可行。

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
typedef long long ll;
queue<pair<int,int>> q;
map<int,bool> vis;
int x[maxn];
vector<int> ans;
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        vis[x[i]] = true;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[x[i] - 1]) {
            q.push(make_pair(x[i] - 1, 1));
            vis[x[i] - 1] = true;
        }
        if (!vis[x[i] + 1]) {
            q.push(make_pair(x[i] + 1, 1));
            vis[x[i] + 1] = true;
        }
    }
    ll ret = 0;
    while (ans.size() < m) {
        pair<int, int> u = q.front();
        ans.push_back(u.first);
        ret += u.second;
        q.pop();
        if (!vis[u.first - 1]) {
            vis[u.first - 1] = true;
            q.push(make_pair(u.first - 1, u.second + 1));
        }
        if (!vis[u.first + 1]) {
            vis[u.first + 1] = true;
            q.push(make_pair(u.first + 1, u.second + 1));
        }
    }
    cout << ret << endl;
    for (int i = 0; i < m; i++)
        cout << ans[i] << (i == m - 1 ? '\n' : ' ');
    return 0;
}

 E.New Year Parties

题目大意:有n个人住在一些房子里,有的人住在同一个房子里。每个人可以选择搬去他的房子左边那个房子或者右边那个房子,亦或是不搬。问这些人最少住几个房子和最多住几个房子。

分析:最多就是尽可能得让所有房子都有人嘛,最少就是尽可能得集中这些人。

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
int x[maxn],n,xx,xxx[maxn];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> xx, x[xx]++, xxx[xx]++;
    for (int i = n + 1; i >= 1; i--) {
        if (x[i] > 1) {
            x[i - 1]++;
            x[i]--;
        }
    }
    for (int i = 0; i <= n; i++) {
        if (x[i] > 1) {
            x[i + 1]++;
            x[i]--;
        }
    }
    int most = 0;
    for (int i = 0; i <= n + 1; i++) {
        if (x[i]) most++;
    }
    int least = 0;
    for (int i = 1; i <= n + 1;) {
        if (xxx[i]) {
            i += 3;
            least++;
        } else {
            i++;
        }
    }
    cout << least << " " << most << endl;
    return 0;
}
点赞
收藏
评论区
推荐文章
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
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Stella981 Stella981
3年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数:59593
Stella981 Stella981
3年前
AndroidStudio封装SDK的那些事
<divclass"markdown\_views"<!flowchart箭头图标勿删<svgxmlns"http://www.w3.org/2000/svg"style"display:none;"<pathstrokelinecap"round"d"M5,00,2.55,5z"id"raphael
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Codeforces Round #565 (Div. 3) C. Lose it!
链接:https://codeforces.com/contest/1176/problem/C(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fcodeforces.com%2Fcontest%2F1176%2Fproblem%2FC)题意:Youare
Stella981 Stella981
3年前
CF 833 B. The Bakery
B.TheBakeryhttp://codeforces.com/contest/833/problem/B(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fcodeforces.com%2Fcontest%2F833%2Fproblem%2FB)题
Stella981 Stella981
3年前
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法参考文章:(1)Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.codeprj.com%2Fblo
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之前把这