D. Range and Partition(贪心 + 双指针)_旅游资讯

D. Range and Partition(贪心 + 双指针)

创始人

2025-05-28 05:03:17

Problem - D - Codeforces

给定一个包含n个整数的数组a，找到一个值范围[æ， y] (z≤y)，并将a分割成恰好k(1≤k≤n)个子数组，如下所示:每个子数组由a的几个连续元素组成，即它等于a1, al+1，…， a，，对于某些l和r (1

Example

input

Copy

2 1

1 2

4 2

1 2 2 2

11 3

5 5 5 1 5 5 1 5 5 5 1

output

Copy

请注意在第一个测试中，应该只有一个子数组，它必须等于整个数组。在[1,2]范围内有2个元素，在[1,2]范围外有O个元素，如果选择的范围为[1,1)，则在(a1)范围内有1个元素，在(a2)范围外有1个元素，则答案无效。在第二个测试中，可以选择范围[2,2]，将数组拆分为子数组(1,3)和子数组(4,4)，在子数组(1,3)中有2个元素在范围内(a2和ag)和1个元素在范围外(a1)，在子数组(4,4)中只有1个元素(a4)，并且在范围内。在第三个测试中，可以选择范围[5,5)，并将数组拆分为子数组(1,4)，(5,7)和(8,11)，在子数组(1,4)中有3个元素在范围内和1个元素在外部，在子数组(5,7)中有2个元素在内部和1个元素在外部，在子数组(8,11)中有3个元素在内部和1个元素在外部。

题解:
假设cnt1为f(l,r)区间在(x,y)范围内的,cnt2为不在的,

f(l,mid) + f(mid+1,r) = f(l,r) 如果f(l,r) > 0

那么f(l,r) == k是不是也可以由一个个小的区间f(l,r) == 1的区间合并过来呢

由于我们是求一个范围,我们先把数组里的数映射到一个数组上,记录哪个数出现几次,

如果要符合题意,应满足

cnt1 - cnt2 == k

cnt1 + cnt2 = n

cnt1 = (n + k) / 2

所以我们应该利用双指针,找到一个最小的,包含这么多数的区间,

找的区间后,输出即可

然后遍历数组,每次区间够1输出即可

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
//#define int long long
const int N = 2e5 + 10;
typedef pair PII;
typedef long long ll;
int a[N],n,k,s[N];
void solve() 
{cin >> n >> k;for(int i = 1;i <= n;i++){scanf("%d",&a[i]);s[a[i]]++;}int len = (k + n + 1)/2;int l = 1,r = n;int sum = 0;int mi = n;for(int i = 1,j = 1;i <= n;i++){while(j <= n&&sum < len){sum += s[j++];}if(sum < len)break;if(j - i < mi){mi = j - i;r = j - 1;l = i;}sum -= s[i];}printf("%d %d\n",l,r);int last = 1;sum = 0;for(int i = 1;i <= n;i++){if(a[i] >= l&&a[i] <= r){sum ++;}else{sum--;}if(sum > 0){if(k != 1){printf("%d %d\n",last,i); }else{printf("%d %d\n",last,n);break;}k --;sum = 0;last = i + 1;}}for(int i = 1;i <= n;i++){s[i] = 0;}
}//1 2 4
signed main() 
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;
scanf("%d",&t);while (t--) {solve();}
}
//1 1 1 0 1//1 1 1 0 1
//1 1 1 0 1
//1 1 1 0 1
//0 1 1 1 1
//0 1 1 1 1

上一篇：河北旅游精选：探秘古城遗迹与自然风光

下一篇：OpenAI 发布GPT-4——全网抢先体验

D. Range and Partition(贪心 + 双指针)

相关内容

热门资讯