首页 > 代码库 > codeforces 250C Movie Critics
codeforces 250C Movie Critics
题目:大意是说
Valentine在想要去看电影,总共n场电影,每场电影都有一个对应的genre值x (1?<=x?<=k),但是
Valentine不想把所有的电影都看完,他想把其中某些genre值=x的电影去掉,只看剩下的电影,但是还有一个问题:就是每场电影的时间是固定的,所以他必须按顺序来观看,当上一场电影的genre值与下一场的genre值不一样的时候,
Valentine的愤怒值就会+1(初始为0),题目要求出去掉genre值为x的电影后,他的愤怒值最小的x。
方法:仔细想了一下之后会发现,需要使用暴力把1-K之间的值遍历一下,求出所有的愤怒值,但是数据量太大,这样肯定会超时,所以就观察一下,如果不去掉任何电影,那么假设他的愤怒值为Y,去掉后为y,那么就是让我们求Y-y的值最大的那个x。让我们来看一个例子:1 3 2,假设要去掉的x=3,根据题目的描述,去掉3后两边的电影值还是不同,所以这样他的总愤怒值Y应该-1,下一个例子:1 3 1,同样去掉3之后,发现两边的电影值相同,那么他的愤怒值应该-2。这样我们就了解了这道题的解决方法。
优化:题目中会出现例如:1 3 3 2的例子,也就是去掉3的时候,还要去掉它后面与它值相同的电影,这样就不如在加载数据的时候把数据直接改为1 3 2,这样会减少很多麻烦。
代码:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int main() { int n,k,x,t=1,s[100010],d[100010]; memset(d,0,sizeof(d)); cin>>n>>k; s[0]=0; for(int i=1;i<=n;i++) { cin>>x; if(x!=s[t-1]) s[t++]=x; } s[0]=s[t]=0; for(int i=1;i<t;i++) { if(s[i-1]==s[i+1]) d[s[i]]+=2; else d[s[i]]+=1; } int p=1; for(int i=2;i<=k;i++) if(d[i]>d[p]) p=i; cout<<p<<endl; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。