题目:计算资源调度器
50分代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;
typedef struct node{
int area;//分区
int id;//节点编号
int task;//任务数量
}node;
bool cmp(const node x,const node y){
if(x.task != y.task){
return x.task<y.task;
}
else{
return x.id<y.id;
}
}
int main()
{
cin>>n>>m;
int area_flag[N];
node nodes[n];
for(int i=0; i<n; i++){
int area;
cin>>area;
area_flag[area] = 1;
nodes[i].area = area;
nodes[i].id = i+1;
nodes[i].task = 0;
}
int g;
cin>>g;
for(int i=0; i<g; i++){
int f,na,pa,paa,paar;
long long a;
cin>>f>>a>>na>>pa>>paa>>paar;
if(na == 0){
sort(nodes,nodes+n+1,cmp);
for(int i=0; i<f; i++){
if(i<n){
cout<<nodes[i].id<<" ";
nodes[i].task++;
}
else{
int t = i%n;
cout<<nodes[t].id<<" ";
nodes[t].task++;
}
}
cout<<endl;
}
else{
if(area_flag[na] != 1){
for(int i=0; i<f; i++){
cout<<0<<" ";
}
cout<<endl;
}
else{
sort(nodes,nodes+n+1,cmp);
while(f){
for(int i=0; i<n; i++){
if(nodes[i].area == na){
cout<<nodes[i].id<<" ";
nodes[i].task++;
f--;
if(f<=0) break;
}
}
}
cout<<endl;
}
}
}
}
从20分到50分,花了很多时间,每次都是因为忽略题目中一种情况,在已有的代码上写不下去了,导致不得不重写,来来回回重写了两三次。而导致这一切的原因是自己将给出的一个特殊示例当成普遍条件,再加上审题不仔细。
虽然自己的目标不是做出满分,但还是需要完全理解题意才行,否则找自己的错误也会浪费很多时间,接着就是对输入输出格式条件认真阅读,不要看个大概,很可能因为漏了其中一句话,就理解完全偏了,做上一次的第三题就遇到了这个问题。
80分代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef struct node{
int area;//分区
int id;//节点编号
int task;//任务数量
set<int> app;
}node;
unordered_map<int,node> nodes;
int main()
{
cin>>n>>m;
vector<int> idsum;
for(int i=1; i<=n; i++){
int a;cin>>a;
idsum.push_back(i);
nodes.insert(pair<int,node>(i,node{a,i,0,set<int>()}));
//nodes[i] = node{a,i,0,set<int>()};
}
int g;cin>>g;
while(g--){
//cout<<"test1"<<endl;
int f,a,na,pa,paa,paar;
cin>>f>>a>>na>>pa>>paa>>paar;
while(f--){
vector<int> temp = idsum,temp2;
if(na!=0){
for(auto i=temp.begin(); i!=temp.end(); ){
//cout<< *i<<":";
//cout<<nodes[*i].area<<" ";
if(nodes[*i].area != na){
//cout<< *i<<endl;
temp.erase(i);
}else i++;
}
}
//cout<<"test2"<<endl;
if(pa!=0){
set<int> ar;
for(auto i=temp.begin(); i!=temp.end();i++){
if(nodes[*i].app.count(pa) !=0){
ar.insert(nodes[*i].area);
//cout<<nodes[*i].area<<endl;
}
}
for(auto i=temp.begin(); i!=temp.end();){
if(ar.count(nodes[*i].area) == 0){
temp.erase(i);
//cout<< *i<<endl;
}else i++;
}
}
//cout<<"test3"<<endl;
temp2 = temp;
if(paa!=0){
for(auto i=temp2.begin(); i!=temp2.end();){
if(nodes[*i].app.count(paa)){
temp2.erase(i);
}else i++;
}
}
if(paar == 1&temp2.empty()|| temp.empty()){
cout<<0<<" ";
continue;
}else if(temp2.empty()&&paar == 0){
temp2 = temp;
}
//cout<<"test4"<<endl;
sort(temp2.begin(),temp2.end(),[](const auto &a,const auto &b)->bool{
if(nodes[a].task != nodes[b].task){
return nodes[a].task<nodes[b].task;
}
else{
return nodes[a].id<nodes[b].id;
}
});
cout<<temp2[0]<<" ";
nodes[temp2[0]].task++;
nodes[temp2[0]].app.insert(a);
cout<<endl;
}
}
80分是借鉴的另一位的思路(link)
主要思路不同在于他不是在原始数组上进行sort操作,而是新开了一个装有节点序号vector,每一次要安排新节点时,就遍历一遍vector,按要求,将不符合的剔除掉(erase函数),最后sort剩下的vector,就能很大程度减少运行时间。
这种思路速度更快,因为会剔除掉无用的之后,每次sort的时间就减少了。而我之前的,每一次都会sort一遍原数组,然后根据要求挑出符合的。这也是编写程序一个重要思路的转变。
所以,有类似于进行排序之后查找的操作,可以转化为,先查找后排序,减少查找的时间。
还有不知道为什么,我的排序方法比参考代码的重构方法要慢一些,所以最终就只得了80分,就很头疼。
这次还重新学习了一下sort的正则表达式,过程中还遇到了一个奇怪的问题。如下:
typedef struct node{
int area;//分区
int id;//节点编号
int task;//任务数量
set<int> app;
}node;
unordered_map<int,node> nodes;
bool cmp(const auto &a,const auto &b){//排序的cmp
if(nodes[a].task != nodes[b].task){
return nodes[a].task<nodes[b].task;
}
else{
return nodes[a].id<nodes[b].id;
}
}
int main(){
vector<int> temp2;
.....//省略
sort(temp2.begin(),temp2.end(),[](const auto &a,const auto &b)
->bool{cmp(a,b);});
感觉这乍一看没什么问题,我在自己的电脑上运行也正常,但放到ccf官网跑就是0分。因为我在官网上看不是编译或者运行错误,说明正常输出。个人猜测,是因为我定义nodes作为全局变量之后,紧接着就就是cmp函数,而这个函数默认会调用未初始化的nodes,使得排序失效,所以输出错误。更新:
按照评论区大佬提醒,自己又测试了一下,确实是少了一个return(躺倒.jpg。而且并不需要用lambda函数,直接用cmp就好,会自动调用函数并且赋值。