[第一波模拟\day1\T2]{分班}(divide.cpp)
【题目描述】
小N,小A,小T又大了一岁了。
现在,他们已经是高二年级的学生了。众所周知,高二的小朋友是要进行文理科分班考试的,这样子的话,三个好朋友说不定就会不分在一个班。
于是三个人决定,都考平均分。。。。。。
当然这不是我们关心的问题。
年级主任Qian,表示分班真的是很头痛。
校长XXY给Qian的分班条件是这样子。
首先由M个学生,分数从高到低已经排序好了。
其次要分成至多N个班。
每个班必须要有至少A个至多B个小朋友。
一个班的学生,他们的分数必须是连在一起的。也就是说,如果第3个小朋友和第5个小朋友在一间教室,第4个小朋友也必须和他们在一起。
最操蛋的是。。。XXY还给出了一个评定分班好不好的标准。
每个学生有一个不知道啥的敏感指数,X[i],1<=i<=M。并且,有一个变量Average =。为了方便计算,Average取下整,注意是先加起来再除,不是每次除再加。
每个教室有一个舒适程度G[i]。而g[i]表示的是第i个小朋友在哪个教室。
现在XXY要求最小化评价指数=∑(每个同学敏感指数-Average)^2 * 该同学分到班级的舒适度Gi
【输入格式】
本题目有多组数据。第一行有一个整数case(<=10),表示有case组数据。
接下来对于每组数据的第一行有4个正整数,依次是M,N,A,B。
第二行有M个正整数,用空格隔开,分别是X[1],X[2] -----X[M]。
第三行有N个正整数,用空格隔开,分别是G[1],G[2] -----G[N]。
【输出格式】
对于每组数据,要输出三个正整数,以空格隔开,不同数据之间要换行。
三个正整数分别为sigma,class,last。分别表示最小的评价指数。在评价指数最小的情况下,安排的教室的最小数目。在评价指数,安排教师数目最小的情况下,最后一个教室的人数的最小数目。
【输入输出样例】
divide.in |
divide.out |
1 10 3 1 4 16 11 12 13 10 15 16 17 18 14 4 5 1 |
186 3 4 |
【样例解释】
前4个,后4个,中间2个。
【数据规模】
编号 |
M |
N |
A B |
X |
G |
1 |
5 |
1 |
1<=A<=B<=M |
1<=X[i]<=10^5 |
-1000<=G[i]<=1000 |
2 |
<=10 |
<=3 |
|||
3 |
<=100 |
<=10 |
|||
4 |
<=1000 |
<=50 |
|||
5 |
<=10000 |
<=200 |
0<=G[i]<=1000 |
||
6 |
|||||
7 |
|||||
8 |
-1000<=G[i]<=1000 |
||||
9 |
|||||
10 |
【题目分析】
设f[i,j]表示将前j个小朋友分到前i个班中的最小评价指数,易写出状态转移方程:
f[i,j] = min {f[i-1,k]+(sum[j]-sum[k])*G[i]} 其中A≤j-k≤ B
sum[i] = ∑(x[i]-Ave)^2
但现在的状态数为10000×200,转移复杂度为O(n),显然会TLE。
将转移方程整理一下:
f[i,j] = min {f[i-1,k]-sum[k]*G[i]}+sum[j]*G[i]
其中j-B≤k≤j-A,i*A<=j<=min(m,i*B)
很明显可用单调队列进行优化
Ans=min{f[i,m]}(1<=i<=n)
Room=i;
Student: for(i=m-b;i<=m-a;i++)//枚举room-1班结束位置
if(f[room-1,i]+G[room]*(sum[m]-sum[i])==Ans)
Stu=m-i;
故可维护一个单调递增队列,每次转移之前将新的可选状态从队列尾插入,且把比其大的都pop出,同时保证队列头的元素在可选范围之内。这样每次转移就可以只取队列头的元素,将转移复杂度降为O(1)。总的时间复杂度为O(n*k),空间复杂度为O(n)。
#include<stdio.h>
#include<string.h>
#define RG register
#define ll long long
const long long oo = 1LL << 60;
#define min(a, b) ((a) < (b) ? (a) : (b))
void read(RG int &x)
{
RG int c = getchar(), f = 1;
for(; c < '0' || c > '9'; c = getchar())
if(c == '-') f = -1;
for(x = 0; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
x *= f;
}
int T, m, n, A, B, room, stu;
ll X[10003], G[203], Aver, f[203][10003], ans;
struct Que
{
int head, tail, ck[10000 + 3];
void fresh() {head = 1; tail = 0;}
void pop_top(RG int p)
{ while(head <= tail && ck[head] + B < p) ++head;}
void push(RG int i, RG ll k, RG int p)
{
while(head <= tail && f[i - 1][ck[tail]] - G[i] * X[ck[tail]] > k) --tail;
ck[++tail] = p;
}
int front() { return ck[head];}
}Q;
int main()
{
freopen("divide.in", "r", stdin);
freopen("divide.out", "w", stdout);
for(read(T); T; --T)
{
read(m), read(n), read(A), read(B);
Aver = 0;
for(RG int i = 1, x; i <= m; ++i) read(x), X[i] = x, Aver += X[i];
Aver /= (ll)m;
for(RG int i = 1; i <= m; ++i) X[i] -= Aver, X[i] *= X[i], X[i] += X[i - 1];
for(RG int i = 1, g; i <= n; ++i) read(g), G[i] = g;
for(RG int i = 0; i <= n; ++i)
for(RG int j = 0; j <= m; ++j) f[i][j] = oo;
f[0][0] = 0;
for(RG int i = 1; i <= n; ++i)
{
Q.fresh();
for(RG int j = i * A; j <= min(i * B, m); ++j)
{
Q.pop_top(j);
Q.push(i, f[i - 1][j - A] - G[i] * X[j - A], j - A);
f[i][j] = f[i - 1][Q.front()] + G[i] * (X[j] - X[Q.front()]);
}
}
ans = oo;
for(RG int i = 1; i <= n; ++i)
if(ans > f[i][m]) ans = f[i][m], room = i;
if(room == 1) stu = m;
else
for(RG int j = m - B; j <= m - A; ++j)
if(f[room - 1][j] + G[room] * (X[m] - X[j]) == ans) stu = m - j;
printf("%I64d %d %d\n", ans, room, stu);
}
fclose(stdin);
fclose(stdout);
return 0;
}
最新文章
- xamarin DependencyService源码阅读
- excel使用技巧
- Multiple Contexts have a path of 错误
- JSON语法五大要素图文介绍
- Ubuntu 16.04 安装mysql并设置远程访问
- word 常用宏代码
- linux下定时执行任务方法【转】
- 【Javascript】: for循环中定义的变量在for循环体外也有效
- BZOJ 3343教主的魔法
- 一种调用opencv库的C++工程通用的Makefile模板
- [Python笔记][第二章Python序列-复杂的数据结构]
- 兔子--Spring基金会
- Chapter 2 Open Book——20
- 如何使用LightningChart拖放功能进行数据转移 ?
- setTimeout 倒计时
- docker 初识之二(简单发布ASP.NET Core 网站)
- C++设计模式——适配器模式
- caffe的cancat层
- Android 开发 获取Android设备的屏幕高宽
- Struts2——namespace、action、以及path问题
热门文章
- java高分局之jstat命令使用
- BZOJ4974(给Next求最小字典序原串)
- Two Flowers CodeChef - TWOFL
- 清橙A1339. JZPLCM(顾昱洲)
- 人品问题 树形dp
- 7.2 Collection和Iterator接口
- Win7下单机版的伪分布式solrCloud环境搭建Tomcat+solr+zookeeper【转】
- oozie.log报提示:org.apache.oozie.service.ServiceException: E0104错误 An Admin needs to install the sharelib with oozie-setup.sh and issue the &#39;oozie admin&#39; CLI command to update sharelib
- 在线编译器Coding Ground
- NIO服务端主要创建过程