本文主要是介绍P9207 灭罪「正直者之死」，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一开始还以为是双向dfs,再一看数据范围,n <= 500,那就肯定不可能是搜索了,必然TLE
这道题最重要的反思就是认真读题,读题有时候太急了,太着急做出来,一直遗漏重要信息,导致做题一直没思路,干着急,这点是真的非常关键
本题要点:
1.认真审题 题目明确说了,是sum <-- sum + a[i],不超范围,其实也就是sum不超范围
2.更改ai的排列顺序,这也就是说可以随便选,不用考虑相对位置
3.尽量多,注意,这个是关键点,我要的是加的数字个数尽量多,而不是数字和尽量大,如果是数字和尽量大这题就真的不太好想,而对于数字个数,就是贪心
我一开始是思路是想着分类讨论,从三个点入手
1. 全部数字 <= 0 那么就是从右往左加,看能加的个数
2. 全部数字 >= 0 那么就是从左往右加, 看能加的个数
3. 存在正负交界,那么就用双指针,左右轮着加
这个思路看似很明确,实际非常难实现,真按照这个思路要写很多特判之类的细节点,非常不好写
而就在这时,我灵光一现!
sum,sum,sum ??? 实际上,注意,我选数的顺序和sum有关系吗??,就是说,只要sum在限定范围内,是
a1 + a2 + a3,还是a3 + a2 + a1,这有区别吗?? 没任何区别,也就是说,事实上,我只需要考虑sum的值在不在范围内就可以
于是,这道题排序 + 前缀和 轻松解决
AC代码如下
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define int int64_t
using namespace std;
int n, k, dn, up;
int a[505],s[505];
signed main() {ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);cin >> n >> k;up = (1 << (k - 1)) - 1;dn = -(1 << (k - 1));int mn = INT_MAX;for (int i = 1; i <= n; ++i) cin >> a[i];sort(a + 1, a + n + 1);for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];int ans = 0;for (int len = n; len >= 1; --len) {for (int l = 1; l + len - 1 <= n; ++l) {int r = l + len - 1;if (dn <= (s[r] - s[l - 1]) && (s[r] - s[l - 1]) <= up) { ans = r - l + 1; break; }}if (ans)break;}cout << ans << endl;return 0;
}这篇关于P9207 灭罪「正直者之死」的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
