2019-2020 ICPC, NERC, Northern Eurasia Finals E. Elections (暴力贪心)

2019-2020 ICPC, NERC, Northern Eurasia Finals E. Elections (暴力&贪心)

题意：给定$n$个候选人，$m$个站点，第$n$个人是反对候选人，每个站点会有$n$个人投票个数。

要求删除最少的站使得第$n$个人的总票数不是严格最多的那个人。

思路：暴力$+$贪心。

我们的目的是使第$n$个人不是严格最多的，那么我们就可以假设最后最多的那个人是$goal$，然后我们可以暴力枚举$goal$对应要删除的站数，然后取最小的即可。

有了$goal$我们就很好贪心的删了，我们取所有站的这两个人票数差，然后由大到小取，直到$cn{t}_{goal}\ge cn{t}_n$即可。

时间复杂度：$O(nmlogm)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int n,m;
int a[N][N],sum[N],tmp[N],mn=1e9;
vector<int>ans,res;
struct cha{
    int id;int x;bool operator<(const cha&c)const{
    return x>c.x; }
}C[N];
int main(){
    scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
    scanf("%d",&a[i][j]);sum[j]+=a[i][j];}}for(int i=1;i<=n;i++) tmp[i]=sum[i];sort(tmp+1,tmp+n+1);if(tmp[n]!=sum[n]||(tmp[n-1]==tmp[n])){
    puts("0");puts("");return 0;} for(int goal=1;goal<n;goal++){
    int sg=sum[goal],sn=sum[n];sn-=sg;ans.clear();for(int i=1;i<=m;i++){
    C[i].x=a[i][n]-a[i][goal];C[i].id=i;}sort(C+1,C+m+1);int cnt=0; for(int i=1;C[i].x>0&&i<=m;i++){
    sn-=C[i].x;cnt++,ans.pb(C[i].id);if(sn<=0) break; }if(sn<=0){
    // printf("goal=%d\n",goal);if(ans.size()<mn){
    res=ans;mn=ans.size();}}}printf("%d\n",mn);for(int i:res) printf("%d ",i);return 0;
}

总结：这种题给了我们一个思考问题的新方向，对于一个问题，我们可以假设答案的结果，然后取依次暴力选取。