codeforces 1283E(贪心)
程序员文章站
2022-07-11 12:01:48
...
题意描述
思路
对于最小值,我们发现如果两个数的差值小于等于2,那么两个数就可以合并在一起。
对于最大值,我们尽可能的让数字向空房子移动,如果移动后还有该数字存在,则尽可能的将数字向后移动。
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=2*1e5+10;
const int M=1e6+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
/*注意边界
清空每个case的影响
注意数据范围
注意证明*/
int a[N],f[N];
void solve(){
int n;cin>>n;
map<int,int> cnt;
rep(i,1,n+1) cin>>a[i],cnt[a[i]]++;
sort(a+1,a+1+n);
f[1]=1;
int last=a[1];
rep(i,2,n+1){
if(a[i]-last<=2){
f[i]=f[i-1];
}else{
f[i]=f[i-1]+1;
last=a[i];
}
}
rep(i,1,n+1){
if(!cnt[i]) continue;
if(cnt[i-1]<=0){
cnt[i-1]++;
cnt[i]--;
}
if(cnt[i]>0){
cnt[i+1]++;
cnt[i]--;
}
}
int mx=0;
for(auto c : cnt ) if(c.y) mx++;
cout<<f[n]<<' '<<mx<<endl;
}
int main(){
IOS;
//int t;cin>>t;
//while(t--)
solve();
return 0;
}
下一篇: 使用git连接码云的远程项目库
推荐阅读
-
Codeforces Round #595 (Div. 3)D1D2 贪心 STL
-
LOJ#515. 「LibreOJ β Round #2」贪心只能过样例(bitset)
-
『ACM C++』 Codeforces | 1066B - Heaters
-
#2861 城市交易 【最大瓶颈路+贪心】
-
『ACM C++』 Codeforces | 1003C - Intense Heat
-
Codeforces 939A题,B题(水题)
-
野生前端的数据结构练习(12)贪心算法
-
CodeForces 29D Ant on the Tree
-
POJ:1017-Packets(贪心+模拟,神烦)
-
HDU 1052(田忌赛马 贪心)