本文共 2046 字，大约阅读时间需要 6 分钟。

#1 1020 C Elections 

选举，之前出过很多次类似的

“样例就是骗你的”

“样例：想不到吧  我的做法只能过样例”

##分析

（思路转个弯儿）

枚举第一个人拿到多少票的时候能够胜利

如果x票胜利的话， 要把所有大于x-1的票都搞成x票，那么他准赢。

比如1票就胜利，那么把所有1票的都拿走才行。

比如2票就胜利，所有2票的都变成1票才行。

你可能会问，那样例不是拿了剩下的吗？

如果2票的那些没动，拿了3个1票的更便宜，其实你枚举的是拿了3票胜利，所以你没管2票的，他们已经构不成威胁了，又贵。

样例： 如果你枚举的是大于2票胜利，拿走了2票的之后，你还没到2票，你只有1票，那就从那么多构不成威胁的里面选最便宜的。

真是个好思路啊。。。 代码在下面。

涉及到多次打乱重新塞入，所以vector排序和插入方便一点

其实仔细分析也还好，讲道理，但是被C和过题人数吓没了呀。。

虽然比赛的时候人数惨淡，但是赛后。。

你把它看得太高了。。  这不就是shabi题吗。。 学习一下zj的写法

（因为第一次把AB都一遍过了吧。。。  ……）

真的看得太高了。。。

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;typedef long long ll;//#define push_back pbint n, m;//n是人数,m是政党的数目ll sum;ll cnt;vector
       
         g[3005];void judge(ll x) {//	cout << x << "--------------" << endl;	sum = 0;/// 票数和花费的钱数啊啊啊	cnt = g[1].size();	for (int i = 2; i <= m; i++) {		if (g[i].size() >= x) { ///如果构成了威胁才去搞他			ll tmp = g[i].size() - x + 1;///动了手脚的数目			cnt += tmp;			for (int k = 0; k < tmp; k++) {				sum += g[i][k];///而且是从最便宜的开始加的				//cout << sum << endl;			}		}	}	if (cnt
        
          all; for (int i = 2; i <= m; i++) { if (g[i].size()
         
          =x) ll tmp = g[i].size() - x + 1; for (int k = tmp ; k < g[i].size(); k++) all.push_back(g[i][k]); } } sort(all.begin(), all.end()); ll k = 0; while (cnt
          
           > n >> m; ll a, b; for (int i = 1; i <= n; i++) { cin >> a >> b; g[a].push_back(b); /// a政党花了的b钱数 } /// 记得排序 记得排序 .. for (int i = 1; i <= m; i++) sort(g[i].begin(), g[i].end()); sum = 0; ll maxx = 1e15+2; for (int i = 1; i <= n / 2+1; i++) { ///枚举后来得到的票数 judge(i); maxx = min(maxx, sum); //cout << sum << endl; sum = 0;/// 用完了要改变回去!! } cout << maxx << endl; return 0;}
          
         
        
       
      
     
    
   

需要注意:

数据范围是1e9的，所以maxn要开1e15呀。

以及，前面提到的g.size()如果是0减去1的时候可能会出问题(下一篇讲了)

还有，中间输出（卡到n/2+1的枚举量）

#2 1025C

每次变化后会发现代码的首尾会连接起来，我们不妨把首尾直接连起来，然后再变化会发现，无论多少次变化字母的相对的顺序就是不变的，我们只要在这个环中相邻连续不相同的数就行了。

相对位置不变的 ...  不知道为啥，好神奇，【大胆猜想】【瞎鸡儿一写竟然过了】【多亏hack我的人让我加了一句break】

嘛，转来转去的题如果造成干扰，写成1234568.。。会发现相对顺序不变-.- 简直神奇  最好是接起来一串(2倍)比较好 

或者:

考虑答案的取值，最优答案可能是一个后缀，或者是一个前缀，或者是一个后缀加上前缀

那么翻转之后最优答案的可选值就有了1的前缀+n的后缀

反正大胆猜想... orx

#3 1023 D

怕的没有写