首页 > 其他分享 >P9797 [NERC2018] Guest Student

P9797 [NERC2018] Guest Student

时间:2023-10-28 21:33:42浏览次数:42  
标签:cnt P9797 int res NERC2018 cin Student 散块 forn

Link

考虑将中间经过的时间分成三段:若干个整星期,前面的散块,后面的散块。

可以先考虑没有前面的散块的做法:

  • 设经过了 \(res\) 个整星期,记每个整星期有 \(cnt\) 天有空,显然中间每次有空都选择听课是最优的,可以发现 \(res=7\times\lfloor\dfrac{k-1}{cnt}\rfloor\),此时剩下需要安排的课程数为 \(k-\lfloor\dfrac{res}{7}\rfloor\times cnt\)。由于剩下的天数不超过 \(7\),所以可以直接扫过整个星期并累加答案。
int get(int x) {
	int res = 7 * ((x - 1) / cnt);
	x -= (res / 7) * cnt;
	for (int i = 1; i <= 7 and x; i++) {
		res++;
		x -= a[i];
	}
	return res;
}

接下来可以发现,前面的散块只有 \(6\) 种情况,即以一个星期的每天作为开头的散块,不妨考虑直接“旋转” a 数组,从星期一开头开始枚举,每次统计完答案直接把开头的元素扔到数组尾部。可以证明,这一做法与直接处理前面的散块是等价的,从而极大地降低了程序地实现难度。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int TestCase, k, a[10], ans, cnt;

void rtt() { // Rotate
	int tmp = a[1];
	for (int i = 1; i < 7; i++) a[i] = a[i + 1];
	a[7] = tmp;
}

int get(int x) {
	int res = 7 * ((x - 1) / cnt);
	x -= (res / 7) * cnt;
	for (int i = 1; i <= 7 and x; i++) {
		res++;
		x -= a[i];
	}
	return res;
}

signed main() {
//Fast IO
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> TestCase;
	while (TestCase--) {
		cin >> k;
		cnt = 0, ans = 1e18;
		for (int i = 1; i <= 7; i++) cin >> a[i], cnt += a[i];
		for (int i = 1; i <= 7; i++) {
			ans = min(ans, get(k));
			rtt();
		}
		cout << ans - 1<< "\n";
	}
}

另给出官方题解供参考:

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

const int N = 7;

int main() {
    int testCaseCount;
    cin >> testCaseCount;
    forn(testCase, testCaseCount) {
        int k;
        cin >> k;
        vector<int> a(N);
        forn(i, N)
            cin >> a[i];
        int sum = accumulate(a.begin(), a.end(), 0);
        int result = INT_MAX;
        forn(i, N)
            if (a[i] == 1) {
                int n = max(0, k / sum - 1);
                int j = i, cur = n * sum, m = n * 7;
                while (cur < k) {
                    cur += a[j];
                    j = (j + 1) % N;
                    m++;
                }
                result = min(result, m);
            }
        cout << result << endl;
    }
}

标签:cnt,P9797,int,res,NERC2018,cin,Student,散块,forn
From: https://www.cnblogs.com/George-Pig-Orz/p/17794690.html

相关文章

  • R语言具有Student-t分布改进的GARCH(1,1)模型的贝叶斯估计|附代码数据
    最近我们被客户要求撰写关于GARCH的研究报告,包括一些图形和统计输出。本说明介绍了具有Student-t改进的GARCH(1,1)模型的贝叶斯估计方法介绍摘要本说明介绍使用Student-t改进的GARCH(1,1)模型对汇率对数收益进行贝叶斯估计。自Engle(1982)的开创性论文以来,使用时间序列模型改变波动率的......
  • Python 继承和子类示例:从 Person 到 Student 的演示
    继承允许我们定义一个类,该类继承另一个类的所有方法和属性。父类是被继承的类,也叫做基类。子类是从另一个类继承的类,也叫做派生类。创建一个父类任何类都可以成为父类,因此语法与创建任何其他类相同:示例,创建一个名为Person的类,具有firstname和lastname属性以及一个printna......
  • Python 继承和子类示例:从 Person 到 Student 的演示
    继承允许我们定义一个类,该类继承另一个类的所有方法和属性。父类是被继承的类,也叫做基类。子类是从另一个类继承的类,也叫做派生类。创建一个父类任何类都可以成为父类,因此语法与创建任何其他类相同:示例,创建一个名为Person的类,具有firstname和lastname属性以及一个printn......
  • Japanese Student Championship 2019 Qualification
    A-TakahashiCalendar枚举\(m\),再枚举\(d_1\),判断一下是否合法即可。#include<iostream>#include<cstdio>usingnamespacestd;intm,d;intmain(){ scanf("%d%d",&m,&d); intans=0; for(inti=1;i<=m;i++) { for(intd10=2;d10<......
  • SQL笔试:Student学生表,Course 课程表,Sc选课表
    tudent学生表(学号,姓名、性别、年龄、组织部门),Course课程表(编号,课程名称),Sc选课表(学号,课程编号,成绩)写一个SQL语句,查询选修了计算机原理的学生学号和姓名select学号,姓名fromStudentwhere学号in(select学号fromScwhere课程编号in(Select课程编号fromCoursewhere课程名......
  • SQL笔试:Student学生表,Course 课程表,Sc选课表
    tudent学生表(学号,姓名、性别、年龄、组织部门),Course课程表(编号,课程名称),Sc选课表(学号,课程编号,成绩)写一个SQL语句,查询选修了计算机原理的学生学号和姓名select学号,姓名fromStudentwhere学号in(select学号fromScwhere课程编号in(Select课程编号fromCoursewhere课程......
  • College Students'Booklist
    CollegeStudents'BooklistAsisclearlyreflectedinthetableabove,thepercentageofthecollegestudents'booklist,from1992to2012.wecanseethereisabigchangeofcollegestudent'schoiceofbooksfrom1992to2012.Obviously,books......
  • [LeetCode] 1349. Maximum Students Taking Exam 参加考试的最大学生数
    Givena m *n matrix seats  thatrepresentseatsdistributions inaclassroom. Ifaseat is broken,itisdenotedby '#' characterotherwiseitisdenotedbya '.' character.Studentscanseetheanswersofthosesittingnexttothele......
  • Japanese Student Championship 2021 F Max Matrix
    洛谷传送门AtCoder传送门我们考虑动态维护答案。如果已经知道上一步的答案,考虑计算这一次操作之后答案的变化。考虑现在有一个数列\(a_{1\simn}\),我们想知道\(\sum\limits_{i=1}^n\max(x,a_i)\)。计算出\(c=\sum\limits_{i=1}^n[a_i<x],s=\sum\limits_{i......
  • Students-system开发步骤
    项目初始化新建文件夹,命名为students-system,注意这里的命名不得为中文或其他特殊字符npminit-y安装包npmijqueryexpressexpress-art-template新建文件夹新建public,views文件夹,public下新建img,js,css文件夹,目录如下:student-systemnode_modulespublicim......