CF 990B B. Micro-World【数组操作/贪心/STL/二分搜索】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了CF 990B B. Micro-World【数组操作/贪心/STL/二分搜索】,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3677字,纯文字阅读大概需要6分钟。
内容图文
【链接】:CF
【题意】:对任意一个数a[i] ,可以对任意 满足 i != j 且 a[i] > a[j] && a[i] <= a[j] +k 的 a[j] 可以被删掉,求使最终剩下的个数最少。
【分析】:扫一遍,二分搜索合法的。
【代码】:
#include<cstdio>
#include<string>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
#include<cctype>
#include<stack>
#include<sstream>
#include<list>
#include<assert.h>
#include<bitset>
#include<numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int maxn = 1e6+ 100;
const int maxm = 100;
const double PI = acos(-1.0);
const double eps = 1e-8;
//const int dx[] = {-1,1,0,0,1,1,-1,-1};
//const int dy[] = {0,0,1,-1,1,-1,1,-1};
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dir[6][3]={ {0,0,1},{0,0,-1},{-1,0,0},{1,0,0},{0,1,0},{0,-1,0} };
int n,k;
int a[maxn], b[maxn];
int main()
{
while(cin>>n>>k)
{
int cnt=0;
for(int i=0;i<n;i++) cin>>a[i];/*
for(int i=0;i<n;i++)
{
cout<<i<<" ";
}
cout<<endl;*/
sort(a,a+n,greater<int>());/*
for(int i=0;i<n;i++)
{
cout<<a[i]<<' ';
}
cout<<endl;*/
for(int i=0;i<n;i++)
{
int p = lower_bound(a,a+n,a[i]+k,greater<int>())-a; //第一个 <= (a[i]+k) 的位置
//cout<<"a[i]+k="<<a[i]+k<<" p="<<p<<" a[p]="<<a[p]<<" a[i]="<<a[i];
if(a[p]>a[i])
{
cnt++;
//cout<<" YES";
}
//cout<<endl;
}
cout<<n-cnt<<endl;
}
}
/*
7 1
101 53 42 102 101 55 54
42 53 54 55 101 101 102
outputCopy
3
42 55 102
inputCopy
6 5
20 15 10 15 20 25
25
outputCopy
1
inputCopy
7 1000000
1 1 1 1 1 1 1
outputCopy
7
7 1
101 53 42 102 101 55 54
101 53 42 102 101 55 54
102 101 101 55 54 53 42
a[i]+k=103 p=0 a[p]=102 a[i]=102
a[i]+k=102 p=0 a[p]=102 a[i]=101 YES
a[i]+k=102 p=0 a[p]=102 a[i]=101 YES
a[i]+k=56 p=3 a[p]=55 a[i]=55
a[i]+k=55 p=3 a[p]=55 a[i]=54 YES
a[i]+k=54 p=4 a[p]=54 a[i]=53 YES
a[i]+k=43 p=6 a[p]=42 a[i]=42
*/
[模拟]
#include<cstdio>
#include<string>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
#include<cctype>
#include<stack>
#include<sstream>
#include<list>
#include<assert.h>
#include<bitset>
#include<numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int maxn = 1e6+ 100;
const int maxm = 100;
const double PI = acos(-1.0);
const double eps = 1e-8;
//const int dx[] = {-1,1,0,0,1,1,-1,-1};
//const int dy[] = {0,0,1,-1,1,-1,1,-1};
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dir[6][3]={ {0,0,1},{0,0,-1},{-1,0,0},{1,0,0},{0,1,0},{0,-1,0} };
int n,k,j;
int a[maxn], b[maxn];
int main()
{
while(cin>>n>>k)
{
int cnt, j=0;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
cnt=n;
for(int i=0;i<n;i++)
{
while(a[j]<a[i])
{
if(a[j]+k>=a[i]) cnt--;
j++;
}
}
cout<<cnt<<endl;
}
}
原文:https://www.cnblogs.com/Roni-i/p/9215028.html
内容总结
以上是互联网集市为您收集整理的CF 990B B. Micro-World【数组操作/贪心/STL/二分搜索】全部内容,希望文章能够帮你解决CF 990B B. Micro-World【数组操作/贪心/STL/二分搜索】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。