学习总结三十

下头论文

# P10605 下头论文

 题目背景

莲子一直在苦恼关于论文的灵感。她为此花了太多时间，以至于没有时间理会她的伙伴梅莉。

 题目描述

一天，莲子发现了一个绝妙的点子，并希望通过实验等过程将其完善。具体来说，她需要依次完成 n 项任务，其中第 $i$ 项任务需要连续的 a_i 天来完成。也就是说，假设她在第 x 天开始该任务，那么她会在第 x+a_i-1 天结束后完成该任务，她需要保证这些天里她都是空闲的。

不幸的是，她有 m天有各种事要去做，这些非空闲的日子会以一个单调递增序列 b的形式给出。即，对于任意的 i(1\leq i<m)，满足 b_i<b_{i+1}。

莲子希望完成任务的时间越短越好。例如：不妨假设，莲子要完成 2项任务，第一项耗时 2天，第二项耗时 3天，而第 4 天莲子有事情要去做。则下图呈现了一种方案，使得莲子完成任务的时间尽可能短，为 7 天：

她想要知道，在最好情况下，她能在第几天结束后完成所有任务。

输入格式

第一行两个整数 n,m。

第二行 n个正整数描述序列 a。

第三行 m个正整数描述序列 b。保证 b 为单调递增序列。

输出格式

一行一个整数，表示莲子最快能在第几天结束后完成所有任务。

输入输出样例 

输入 
2 1
2 3
4

输出 
7
输入 
3 3
1 1 1
1 5 6

输出 
4

题意读懂就是有n项任务，必须依次完成，第i项任务对应需要a_i天，从第x天开始，再x+a_i-1天后结束。有m天是忙碌的，b_i表示第x天是忙碌的。所以我们要判断我们完成任务的时间里有没有忙碌的一天，如果有，休息一天（忙碌的那天的前一天），从忙碌的那天后再判断。 

例子解释清楚了，代码如下：

#include<iostream>
using namespace std;
int n, m,ans=1,now=1;
int a[1005],b[1005];
int main()
{cin >> n >> m;for (int i = 1; i <=n; i++){cin >> a[i];}for (int i = 1; i <=m; i++){cin >> b[i];}for (int i = 1; i <= n; i++){while (!(ans != b[now] && ans + a[i] - 1 < b[now]) && now <= m) {ans = b[now] + 1;now++;}ans =ans+ a[i] - 1;if (i != n) {ans++;}}cout << ans;return 0;
}

 第二个判断语句if (i != n)  {ans++；}为什么会有这个？i！=n表示判断当前任务是否为最后一项任务，ans++，如果不是最后一项任务的情况下，当前任务与开始下一次任务之间留出一天的空闲时间。如果没有这个语句，第二个案例会输出2。

单项链表

基本知识

1.节点的基本结构：

struct Node {int data;Node* next;//指向下一节点的指针
};

2.插入节点至链表的结尾：

#include<iostream>
using namespace std;
struct Node {int data;Node* next;//指向下一节点的指针
};
Node* head, * p, * r;//链表的头，当前，尾指针
int x;
int main()
{cin >> x;head = new Node;r = head;while (x != -1){p = new Node;p->data = x;p->next = NULL;r->next = p;r = p;cin >> x;}return 0;
}

3.查询链表中的元素

while (p->next != NULL)
{if (p->data == target) {cout << "find it" << endl;}
}

看题：

题解很简单，我自己尝试实现一下，结果只有10分。。。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
struct Node {int next;
}Nodes[10005];
int main()
{int n;scanf("%d", &n);while (n--){int a, b, c;scanf("%d", &a);if (a == 1) {scanf("%d%d", &b, &c);Nodes[b].next = c;Nodes[c].next = Nodes[b].next;}if (a == 2) {scanf("%d", &b);printf("%d", Nodes[b].next);}if (a == 3) {scanf("%d", &b);Nodes[b].next = Nodes[Nodes[b].next].next;}}return 0;
}

 第三步我是问了ai，实在是想不出来。后来再CSDN找到一个大佬写的题解，感觉差别不是很大，但他可以过，大佬不愧是大佬。

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N];
void insert() {int x, y;cin >> x >> y;a[y] = a[x];//将y的下一个节点设置为x当前的下一个节点a[x] = y;//x的下一个节点设置y
}
void find()
{int x;cin >> x;cout << a[x] << endl;
}
void del()
{int x;cin >> x;a[x] = a[a[x]];//跳过当前x的下一个节点，实现删除
}
int main()
{int n;cin >> n;while (n--){int t;cin >> t;switch (t) {case 1:insert(); break;case 2:find(); break;case 3:del(); break;}}return 0;
}