网站开发成本计算,铁道部建设监理协会网站查询,行业网站,263企业邮箱后缀是什么来来来#xff0c;走过路过不要错过题目题解代码实现1代码实现2题目
⼩Y同学有⼀块超级CPU#xff0c;它有两个超级核⼼A和B。
A核⼼可以同时处理多项任务#xff0c;每项任务处理时间为x#xff0c;B核⼼只能同时处理⼀项任务#xff0c;每项任务处理时间为y。
这⼀天…
来来来走过路过不要错过题目题解代码实现1代码实现2题目
⼩Y同学有⼀块超级CPU它有两个超级核⼼A和B。
A核⼼可以同时处理多项任务每项任务处理时间为xB核⼼只能同时处理⼀项任务每项任务处理时间为y。
这⼀天⼩Y同学接到了n项紧急任务第i项紧急任务在ti时刻发出且必须在任务发出时进⾏处理。 由于⼩Y可以调节CPU的B核⼼你想知道对于y∈1,x处理完毕所有任务的最早时间是多少
输入格式 第⼀⾏两个整数n,x表⽰紧急任务数量及A核⼼对每项任务的处理时间。 第⼆⾏n个整数ti表⽰第i个紧急任务发出的时间ti。 输出格式 共x⾏第i(1≤i≤x)⾏⼀个整数表⽰当yi时的答案ans。
样例 样例输入1 3 3 1 2 3 样例输出1 4 5 6 样例输入2 3 5 1 4 5 样例输出2 6 9 9 9 10 数据范围与提示 样例输入输出解释1: y1的时候:t11任务交给核⼼A,t22,t33两个任务交给核⼼B,结束时刻是4,这是最早的⼀种完成的⽅案。 y2的时候:t11,t33两个任务交给核⼼B,t22任务交给核⼼A,结束时刻是5,这是最早的⼀种完成的⽅案。 y3的时候:t11,t22两个任务交给核⼼A,t33任务交给核⼼B,结束时刻是6,这是最早的⼀种完成的⽅案。
数据范围 对于40%的数据1≤n≤103 对于100%的数据1≤nx≤1060≤ti-1≤ti≤109
题解
初见这道题的时候一行扫下来贪心应该是跃然纸上我就没必要解释了吧 每次拿到题一定要先观察数据范围 40%告诉我们当你完全没有思路的时候就可以暴力得到40 100%告诉我们我们只能运用nx的范围因为1e9一秒肯定是会被T掉的 所以我们就能大概推出这份正解的时间复杂度应该是O(n)O(n)O(n)左右 贪心就更加有信心了 首先通读题目后应该了解求得就是最后一个任务的完成时间 我们就从最后一个开始思考 题目告诉了y永远小于等于x 那么最后一个n任务肯定是交给y去完成一定是优于或者等于交给x完成 所以说x? 贪心思想就呼之欲出了 B核心只能一次进行一个任务而A可以多个连续进行 所以最晚的完成时间就是? n任务交给B完成的时间和最后一个任务交给A完成的时间的最大值 接下来我们就是思考如何去找到最后一个交给A完成的任务i 我们知道当i与j任务的时间差大于等于y的时候i和j任务都可以由B去完成 这就启示我们去找到最后一个任务i的时间与n任务的时间差小于y 这个i就必须交给A去完成作差的方法就是AC实现
因为是求最后一个其实我们转化一下就是从后往前找的第一个 用一个数组去存当yi时最后一个i的下标这个y的处理一个n循环就可以完成了 下面分享两种代码本质上应该都是一样的但理解可能有难易之分
代码实现1
#include cstdio
#include iostream
using namespace std;
#define MAXN 1000005
int n, x;
int t[MAXN], result[MAXN];
int main() {scanf ( %d %d, n, x );for ( int i 1;i n;i )scanf ( %d, t[i] );int tmp x;for ( int i n;i 1;i -- ) {int ip t[i] - t[i - 1];while ( ip tmp tmp 0 ) {result[tmp] i - 1;tmp --;}if ( ! tmp ) break;}for ( int i 1;i x;i )printf ( %d\n, max ( t[result[i]] x, t[n] i ) );return 0;
}代码实现2
#include cstdio
#include iostream
using namespace std;
#define MAXN 1000005
int n, x;
int t[MAXN], vis[MAXN];
int main() {scanf ( %d %d, n, x );for ( int i 1;i n;i )scanf ( %d, t[i] );for ( int i n;i 1;i -- ) {int ip t[i] - t[i - 1];ip ;for ( int j ip;j x ! vis[j];j )vis[j] i - 1;}for ( int i 1;i x;i )printf ( %d\n, max ( t[vis[i]] x, t[n] i ) );return 0;
}好了这道题就到此为止
