2 条题解

  • 0
    @ 2025-10-8 17:00:42
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 200;
    struct node { int x, id; } a[N];
    bool cmp(node n1, node n2) {
        return n1.x < n2.x;
    }
    int main() {
        int k; scanf("%d", &k); 
        int n = 3 * k;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i].x);
            a[i].id = i;
        }
        sort(a + 1, a + n + 1, cmp); 
        for (int i = 1; i <= k; i++) printf("%d\n", a[i].id);
        
        random_device rd;
        mt19937 rng(rd());
        while (1) {
            int sum = 0, res = 0, t = k * 500;
            for (int i = k + 1; i <= 2 * k; i++) sum += a[i].x;
            res += (sum > t); sum = 0;
            for (int i = 2 * k + 1; i <= n; i++) sum += a[i].x;
            res += (sum > t); sum = 0;
            if (res == 2) {
                for (int i = k + 1; i <= n; i++) printf("%d\n", a[i].id);
                break;
            }
            shuffle(a + k + 2, a + n + 1, rng);
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 17:00:37
      #include<bits/stdc++.h>
      using namespace std;
      const int N=200;
      struct node{int x, id;} a[N];
      bool cmp(node n1, node n2){
      	return n1.x<n2.x;
      }
      int main(){
      	int k; scanf("%d", &k); 
      	int n=3*k;
      	for(int i=1; i<=n; i++){
      		scanf("%d", &a[i].x);
      		a[i].id=i;
      	}
      	sort(a+1, a+n+1, cmp); 
      	for(int i=1; i<=k; i++) printf("%d\n", a[i].id);
      	
      	random_device rd;
      	mt19937 rng(rd());
      	while(1){
      		int sum=0, res=0, t=k*500;
      		for(int i=k+1; i<=2*k; i++) sum+=a[i].x;
      		res+=(sum>t); sum=0;
      		for(int i=2*k+1; i<=n; i++) sum+=a[i].x;
      		res+=(sum>t); sum=0;
      		if(res==2){
      			for(int i=k+1; i<=n; i++) printf("%d\n", a[i].id);
      			break;
      		}
      		shuffle(a+k+2, a+n+1, rng);
      	}
      	return 0;
      }
      • 1

      USACO(121)随机化/动态规划(背包型)9:三个代表P1675 [USACO05FEB] Jersey Politics

      信息

      ID
      2312
      时间
      1000ms
      内存
      256MiB
      难度
      8
      标签
      递交数
      16
      已通过
      5
      上传者