题目链接
解题思路
每组输入后对龙脖子的直径和骑士的能力值进行从小到大排序,外加一个判断数组判断该骑士是否被雇佣
然后遍历每个龙,看没有雇佣过的骑士是否可以杀死,因为已经从小到大排序,所以最后的结果为最小花费
循环结束判断所有的龙是否被杀死
解题代码
#include <bits/stdc++.h> using namespace std; bool complare( int a, int b ) { return a<b; } int main() { while ( true ) { int n; int m; cin >> n >> m; if ( n==0&&m==0 ) return 0; int d[n];//龙 for ( int i=0; i<n; i++ ) { cin >> d[i]; } int q[m];//骑士 for ( int i=0; i<m; i++ ) { cin >> q[i]; } if ( n>m ) { cout << "Loowater is doomed!" << endl; break; } int is[m]; for ( int i=0; i<m; i++ ) { is[i] = 1; } //排序 sort( d, d+n, complare ); sort( q, q+m, complare ); // for ( int i=0; i<m; i++ ) { // cout << is[i] << " "; // } int sum = 0;//花费 int cnt = 0;//杀死的龙 for ( int i=0; i<n; i++ ) { int num = d[i]; for ( int j=0; j<m; j++ ) { if( q[j]>=num && is[j]==1 ) { sum += q[j]; is[j] = 0; cnt++; break; } } } if ( cnt==n ) { //所有的龙被杀死 cout << sum << endl; } else { cout << "Loowater is doomed!" << endl; } } }