I sometimes get confused when to use greedy and when to use DP. I have this problem — https://mirror.codeforces.com/contest/455/problem/A where I thought my solution which is greedy would be correct but it went wrong on a 100 element array when submitted. I don't seem to find any mistake or failing test case for my solution. Can someone help? ↵
↵
<spoiler summary="My Solution">↵
#include <iostream>↵
#include <queue>↵
#include <vector>↵
#include <map>↵
↵
using namespace std;↵
↵
#define int long long↵
using namespace std;↵
↵
signed main(){↵
int n;cin>>n;↵
vector<int> v(n);↵
for (int i=0;i<n;++i) cin>>v[i];↵
vector<int>isneighbor(1e5+5,0);↵
vector<int>ele(1e5+5,0);↵
for(int i=0;i<n;++i){↵
ele[v[i]]+=1;↵
}↵
priority_queue<pair<int,int>>pq;↵
for(int i=0;i<n;++i){↵
int sum=0;↵
sum += v[i] + ele[v[i]-1]*(v[i]-1) + ele[v[i]+1]*(v[i]+1);↵
pq.push({-sum,v[i]});↵
}↵
int ans = 0;↵
while(!pq.empty()){↵
pair<int,int> pii = pq.top();↵
pq.pop();↵
int curr = pii.second;↵
if (isneighbor[curr]) continue;↵
ans += curr;↵
isneighbor[curr-1] = 1;↵
isneighbor[curr+1] = 1;↵
}↵
cout<<ans<<'\n';↵
}↵
</spoiler>↵
↵
↵
<spoiler summary="My Solution">↵
#include <queue>↵
#include <vector>↵
#include <map>↵
↵
using namespace std;↵
↵
#define int long long
using namespace std;↵
↵
signed main(){↵
int n;cin>>n;↵
vector<int> v(n);↵
for (int i=0;i<n;++i) cin>>v[i];↵
vector<int>isneighbor(1e5+5,0);↵
vector<int>ele(1e5+5,0);↵
for(int i=0;i<n;++i){↵
ele[v[i]]+=1;↵
}↵
priority_queue<pair<int,int>>pq;↵
for(int i=0;i<n;++i){↵
int sum=0;↵
sum += v[i] + ele[v[i]-1]*(v[i]-1) + ele[v[i]+1]*(v[i]+1);↵
pq.push({-sum,v[i]});↵
}↵
int ans = 0;↵
while(!pq.empty()){↵
pair<int,int> pii = pq.top();↵
pq.pop();↵
int curr = pii.second;↵
if (isneighbor[curr]) continue;↵
ans += curr;↵
isneighbor[curr-1] = 1;↵
isneighbor[curr+1] = 1;↵
}↵
cout<<ans<<'\n';↵
}↵
</spoiler>↵
↵
