5 条题解
-
17
思路
这道题可以先存储一个双向链表n个的结点，第i个结点的数值为i，前一个结点为i-1和后一个结点为i+1，比如第10个结点数值为10，前一个结点是9，下一个结点是11。 $\\$接下来，按照a数组中数的顺序逐个删除双向链表中的结点。每个结点被删除时，由于比它小的数都一定先被删去了，所以它的下一个结点的编号就是题目要求的，右边第一个比它大的数的下标。 例如首先删除1号结点，让0号结点和2号结点直接相连，然后删除4号结点，让3号结点和5号结点直接相连。从链表结构上来说，1号结点和4号结点已经不在链表中，但是两个结点没有在内存中消失，它们的上个结点和下个结点的数据仍然存在，并且下个结点的编号就是它的右边第一个比它大的数的下标。然后继续删除接下来的3个结点，5号，3号和2号，就可以得到答案，答案就存储在每个结点的nxt中。代码
#include <iostream> using namespace std; int n, x, a[100010]; struct Node { int pre, nxt; } node[100005]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> x; a[x] = i; } for (int i = 1; i <= n; i++) { node[i].nxt = i + 1; node[i].pre = i - 1; } for (int i = 1; i <= n; i++) { node[node[a[i]].nxt].pre = node[a[i]].pre; node[node[a[i]].pre].nxt = node[a[i]].nxt; } for (int i = 1; i <= n; i++) { cout << node[i].nxt << " "; } return 0; }-
hetao1581989 @ 2023-8-17 11:43:08
下标计数？
-
👍👍 👍 👍 👍
-
高级思想，高端算法👍 😄
-
👍
-
-
3
hetao24883491
LV 10
@ 2023-7-25 11:21:45
类似于“小鱼比可爱”这道题。 这道题标明时间复杂度为O(n*n)，暴力枚举就行了。
#include <iostream> using namespace std; int main(void){ int N,a[100000]; cin>>N; for(int i=1;i<=N;i++) cin>>a[i]; for(int i=1;i<=N;i++){ int ans=N+1; for(int n=i+1;n<=N;n++) if(a[i]<a[n]){ ans=n; break; //跳出 } cout<<ans<<' '; } return 0; }-
hetao2753405
@ 2023-8-9 22:16:19
牛
-
人家叫你O（n）的时间复杂度
-
-
2
-
这道题可以直接看2018年普及组最后一题 链接：2018普及组（自己调到最后一题） 好了，接下来是代码：
代码
#include <iostream> using namespace std; int n; int L[100010],R[100010],a[100010]; int main(){ cin>>n; for(int i=1;i<=n;i++){ int x; cin>>x; a[x]=i; } for(int i=1;i<=n;i++){ R[i]=i+1; L[i]=i-1; } for(int i=1;i<=n;i++){ L[R[a[i]]]=L[a[i]]; R[L[a[i]]]=R[a[i]]; } for(int i=1;i<=n;i++){ cout<<R[i]<<" "; } return 0; }请接着往下看
- 当然，原题是这样的：（把多余的空行删了）
原题
好吧，这才是原题
#include <iostream> using namespace std; const int N = 100010; int n; int L[N], R[N], a[N]; int main() { cin >> n; for (int i = 1; i <= n; ++i) { int x; cin >> x; ① ; } for (int i = 1; i <= n; ++i) { R[i] = ② ; L[i] = i - 1; } for (int i = 1; i <= n; ++i) { L[ ③ ] = L[a[i]]; R[L[a[i]]] = R[ ④ ]; } for (int i = 1; i <= n; ++i) { cout << ⑤ << " "; } cout << endl; return 0; }题目答案
①：a[x]=i ②：i+1 ③：R[a[i]] ④：a[i] ⑤：R[i]
</li> </ul>
-
-
1
#include <iostream> #define MAXN 100005 int n, a[MAXN], s = 0; bool tmp = false; int main() { scanf("%d", &n); // int m = n; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 1; i <= n; i++) { tmp = false; s = 0; for (int j = i; j <= n; j++) { if (a[i] < a[j]) { tmp = true; s = j; break; } } if (tmp) { printf("%d ", s); } else { printf("%d ", n + 1); // std:: cout << 6 << " "; } } return 0; } ```好简单 -
-4
hetao1897892 LV 8 @ 2023-7-25 15:15:52
精品题解
FROM:丁丁
代码
#include"iostream" #include"ctime" #include"cstdlib" #define MAX 20000 using namespace std; struct element{ //用来排序的数据结构 int data; // 数据 int index; // 序号 }; int cmp(const void *a,const void *b); //升序排列 void rand_of_n(int a[],int n); //产生 1-n 的随机排列并存到 a[] 中 int main(){ int a[MAX]; int i,n=10; rand_of_n(a,n); for(i=0;i<n;i++) cout<<a[i]<<" "; return 0; } int cmp(const void *a,const void *b){ // 升序排序 return((struct element*)a)->data - ((struct element*)b)->data; } void rand_of_n(int a[],int n){ int i; struct element ele[MAX]; srand((int)time(0)); // 初始化随机数种子 for(i=0;i<n;i++){ ele[i].data=rand(); // 随机生成一个数 ele[i].index=i+1; } qsort(ele,n,sizeof(ele[0]),cmp); //排序 for(i=0;i<n;i++){ a[i]=ele[i].index; } }别打开
这个代码超过了99%的选手理解别打开！！
好吧 AC代码#include <iostream> using namespace std; int n, x, a[100010]; struct Node { int pre, nxt; } node[100005]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> x; a[x] = i; } for (int i = 1; i <= n; i++) { node[i].nxt = i + 1; node[i].pre = i - 1; } for (int i = 1; i <= n; i++) { node[node[a[i]].nxt].pre = node[a[i]].pre; node[node[a[i]].pre].nxt = node[a[i]].nxt; } for (int i = 1; i <= n; i++) { cout << node[i].nxt << " "; } return 0; }-
hetao8554411
@ 2023-7-28 10:14:58
&抄我技术？ 看来你也知道三角怎么打出来了&
-
？！
-
你搁那做游戏啊！！！
-
张子轩 @ 2024-6-13 11:26:35
&ddjfjdiijn&
-
yiyun
LV 3
MOD
@ 2023-7-6 16:23:59
- 1