第一题
给出一条长度为 L
的线段,除了头和尾两个点以外,上面还有 n
个整数点,需要在上面再放 k
个新的点,使得相邻的两个点之间的最大距离最小,求这个最小的距离。
题解
我当时太紧张了,真是脑抽了,还想着弄个优先队列,划分最大的,然后丢进去,再划分最大的,但是是错的。
正确解法小姐姐走了我才想起来,二分答案 m
,然后扫描一遍判断将每一段划分成小于等于 m
的一共需要多少次。如果次数大于 k
,说明 m
太短了,否则说明 m
太长了。
代码
intmain() { intL, n, k; scanf("%d%d%d", &L, &n, &k); vector<int>a(n+2, 0); a[0] =1; for (inti=1; i<=n; ++i) { scanf("%d", &a[i]); } a[n+1] =L; intl=1, r=L-1; while (l<r) { intm=l+ (r-l) /2; intcnt=0; for (inti=1; i<=n+1; ++i) { cnt+= (a[i] -a[i-1] -1) /m; } if (cnt>k) l=m+1; elser=m; } cout<<l<<endl; return0;}
第二题
给出一个数组 A
,找到最大的 A[i] - A[j]
,要求 i > j
。
题解
这题很简单,直接遍历每个 A[i]
,维护它前面最小的那个数 minn
,然后求出最大的 A[i] - minn
就行了。
代码
intmain() { intn; scanf("%d", &n); vector<int>a(n, 0); for (inti=0; i<n; ++i) { scanf("%d", &a[i]); } intminn=a[0], res=INT_MIN; for (inti=1; i<n; ++i) { res=max(res, a[i]-minn); minn=min(minn, a[i]); } cout<<res<<endl;}
第三题
给定一个字符串,对该字符串进行删除操作,保留 k
个字符且相对位置不变,使字典序最小。
题解
这题也脑抽了,想了一堆方法,dp
复杂度太高,线段树太麻烦,最后用 map
勉强写了一下。
主要思想是这样的,最后要保留 k
个字符,那么第一个字符只能在下标 0 ~ n-k
中寻找,那肯定找最小的啊,如果有多个就找最前面那个,把它的位置记为 pos
。
然后第二个字符肯定得在下标 pos ~ n-k+1
中寻找,还是一样的思路,找到以后更新 pos
位置,依次找下去找到 k
个为止。
所以我就利用了 map
的特性,把寻找窗口内的字符个数做一下统计,然后取出 map
中的第一个字符就是字典序最小的了,次数减一,如果减到 0 了就删除掉。
然后从 pos
位置开始遍历,直到第一个等于你刚刚取出的字符为止,更新 pos
位置。
最优解:
最优解当时没想出来,是用单调栈。维护一个递增的单调栈,我们的目标是保留 k
个字符,也就是删除 n-k
个字符。
那么如果栈顶元素大于当前遍历元素,并且还没删够 n-k
个,就出栈,当作删除了一个元素。否则的话如果删够了,不管大小关系统统入栈,因为你没法删了。
最后全遍历完了,如果还没删够,那就继续出栈,直到删够为止。最后把栈里的字符拼接成一个字符串就是答案了。
时间复杂度是 的。
代码
stringf(strings, intk) { intn=s.size(); map<char, int>mp; for (inti=0; i<=n-k; ++i) { mp[s[i]]++; } stringres=""; intpos=0; for (inti=k; i>=1; --i) { charc=mp.begin()->first; res+=c; for (intj=pos; j<=n-i; ++j) { mp[s[j]]--; if (!mp[s[j]]) mp.erase(s[j]); if (s[j] ==c) break; mp[s[n-i+1]]++; } returnres;} intmain() { strings; intk; cin>>s>>k; cout<<f(s, k) <<endl;}
最优解:
stringf(strings, intk) { intn=s.size(); k=n-k; stack<char>st; for (inti=0; i<n; ++i) { while (!st.empty() &&st.top() >s[i] &&k) { st.pop(); k--; } st.push(s[i]); } stringres=""; while (!st.empty() ) { if (k) k--; elseres+=st.top(); st.pop(); } reverse(res.begin(), res.end() ); returnres;} intmain() { strings; intk; cin>>s>>k; cout<<f(s, k) <<endl; }
作者简介:godweiyang,知乎同名,华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~