网站管理和维护,门户网站开发公司平台,商务服务平台,月光博客 网站模板太戈编程1655题
一条直线上#xff0c;你安排了n个哨兵站岗放哨#xff0c;编号从1到n。其中i号哨兵的坐标位置是x[i]。不会有哨兵站在相同的位置。作为指挥官#xff0c;你需要知道3个信息#xff1a;
1.从左到右#xff0c;每个哨兵的坐标依次是几?
2.从左到右…太戈编程1655题
一条直线上你安排了n个哨兵站岗放哨编号从1到n。其中i号哨兵的坐标位置是x[i]。不会有哨兵站在相同的位置。作为指挥官你需要知道3个信息
1.从左到右每个哨兵的坐标依次是几?
2.从左到右每个哨兵依次是几号哨兵?
3.哨兵编号从1到n每个哨兵依次站在从左到右的第几个?
离散化
什么是离散化呢数据离散化处理_哔哩哔哩_bilibili
给出一列数字在有些情况下这些数字的值的绝对大小并不重要而相对大小很重要。例如对一个班级学生的成绩进行排名此时不关心成绩的绝对值只需要输出排名如分数为{95507221}排名为{1324}。
“离散化”就是用数字的相对值替代它们的绝对值。离散化是一种数据处理的技巧它把分布广而稀疏的数据转换为密集分布从而能让算法更快速、更省空间的处理。步骤1.排序 2.离散化 3.归位
离散化手工编码
#include bits/stdc.h
using namespace std;
const int N500010;
struct data{int val;int id;
}olda[N];
int newa[N];
bool cmp(data x,data y){return x.valy.val;
}
int main(){int n;cinn;for(int i1;in;i){cinolda[i].val;olda[i].idi;}sort(olda1,olda1n,cmp);for(int i1;in;i){newa[olda[i].id]i;}for(int i1;in;i) coutnewa[i];return 0;
}
那么回到1655这题应该怎么做呢
#include bits/stdc.h
using namespace std;
const int N100009;
int rk[N];
struct guard{//结构体int x,id;
};
guard g[N];
bool cmp(const guardu,const guardv){//排序return u.xv.x;
}
int main()
{freopen(guard.in,r,stdin);freopen(guard.out,w,stdout);int n;cinn; for(int i1;in;i) cing[i].x;for(int i1;in;i) g[i].idi;//学号赋值sort(g1,g1n,cmp);for(int i1;in;i) rk[g[i].id]i;for(int i1;in-1;i) coutg[i].x ;coutg[n].xendl; for(int i1;in-1;i) coutg[i].id ;coutg[n].idendl; for(int i1;in-1;i) coutrk[i] ; coutrk[n]endl;return 0;
}
太戈编程56题
某校大门外长度为L的马路上有一排树每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴马路的一端在数轴0的位置另一端在L的位置数轴上的每个整数点即012……L都种有一棵树 由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数区域之间可能有重合的部分。现在要把这些区域中的树包括区域端点处的两棵树移走。你的任务是计算将这些树都移走后马路上还有多少棵树
差分 cinlm;
for(int i1;im;i){cinab;if(ab) swap(a,b);a;b;//确保都为正整数d[a];d[b1]--;
} 那么第5行我为什么敢无缘无故1呢这都是缓冲格的帮助。
然后呢
#include bits/stdc.h
using namespace std;
const int N1000009;
int l,m,a,b,s[N],d[N];
int main(){freopen(tree.in,r,stdin);freopen(tree.out,w,stdout);cinlm;for(int i1;im;i){cinab;if(ab) swap(a,b);a;b;d[a];d[b1]--;}int ansl1;for(int i1;il1;i){s[i]s[i-1]d[i];if(s[i]) ans--;}coutansendl;return 0;
}
但是……如果303题怎么办呢
太戈编程303题
#include bits/stdc.h
using namespace std;
const int M1000000009;
struct pnt{int x,tag;
}p[M];
bool cmp(const inta,const intb){if(p[a].xp[b].x) return 1;if(p[a].xp[b].x) return 0;if(p[a].tagp[b].tag) return 1;return 0;
}
int main(){int l,m;cinlm;for(int i1;im;i){int a,b;cinab;if(ab) swap(a,b);a;b;p[i].xa;p[i].tag1;p[im].xb1;p[im].tag-1;}for(int i1;i2*m;i) id[i]i;sort(id1,id12*m,cmp);int ansl1,pre0;for(int i1;i2*m;i){if(s[i-1]) ans-p[id[i]].x-pre;prep[id[i]].x;s[i]s[i-1]p[id[i]].tag;}coutansendl;
}
希望这些对大家有用三连必回
