因为今天要打CF,所以就先去做了以前的题试试水
不得不说,CF的题做起来确实有意思,不过英语差也是让人头疼的一点
机翻质量谁试谁知道
这道作为Div.2的T1,确实很水 因为语言不通看不懂题意强行卡了半个小时
题意见 点这里
说说解题思路,每一次的选择都是两人份,所以很明显的一个贪心
如果能满足两个人及以上,就尽可能满足,否则就选满足一个人的.
事后看题解有好多大佬有特别简单的做法 我真是弱啊
这里为了快速找到每次能选的数量最多的类型,我用了一个优先队列其实压根不用这么麻烦
代码如下咯越看越觉得写的又臭又长
#include<bits/stdc++.h> using namespace std; #define ll long long #define rg register #define maxn 5000 inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c<='9'&&c>='0') { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x*f; } struct node { int num;//数字 int tot;//数量 bool operator < (const node &a) const { return tot<a.tot; } }s[maxn]; priority_queue<node>q; int cnt; int n,k; bool vis[maxn]; int last[maxn]; int main() { n=read(),k=read(); int ts=(int)(double)ceil(n*1.0/2.0); for(rg int i=1;i<=n;++i) { s[i].num=read(); if(vis[s[i].num]==0) { vis[s[i].num]=1; last[s[i].num]=i; s[i].tot++; } else { s[last[s[i].num]].tot++; } } memset(vis,0,sizeof(vis)); for(rg int i=1;i<=n;++i) { if(vis[s[i].num]==0) { q.push(s[i]); vis[s[i].num]=1; } } node now=q.top(); while(ts--) { node now=q.top(); if(now.tot>=2) { cnt+=2; now.tot-=2; q.pop(); q.push(now); } else if(now.tot==1) { cnt++; now.tot=0; q.pop(); q.push(now); } else q.pop(); } cout<<cnt; }