A.Anagram
C.Cities
E.Sequence
C.Cities
签到题
思路:找出一个代价最小的点,用它连接其他所有的点
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int q[N];
int main ( void )
{
ios::sync_with_stdio ( false );
cin.tie(0);
int T;
cin >> T;
while ( T-- )
{
ll res, min = 0x3f3f3f3f, min_sit;
res = 0;
int n;
cin >> n;
for ( int i = 1; i <= n; i++ )
{
cin >> q[i];
if ( q[i] < min ) min = q[i], min_sit = i;
}
for ( int i = 1; i <= n; i++ )
{
if ( i != min_sit )
{
res += ( q[i] + min );
}
}
cout << res << endl;
}
return 0;
}
时间复杂度 \(O(N)\)
A.Anagram
贪心思维题/签到
题面:给定两个字符串,计算他们之间的最小差异值
思路:重排序两个字符串的内部的字符,按照其字符大小排序,然后对比相应位数上的差异值,最后将第一个字符串移位,再次对比,依此重复。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main ( void )
{
string a, b;
while ( cin >> a >> b )
{
vector<char> x, y;
for ( int i = 0; i < a.size(); i++ )
x.push_back ( a[i] );
for ( int i = 0; i < b.size(); i++ )
y.push_back ( b[i] );
sort ( x.begin(), x.end() );
sort ( y.begin(), y.end() );
int res = 0x3f3f3f3f;
for ( int i = 0; i < x.size(); i++ )
{
int t = 0;
for ( int j = 0; j < x.size(); j++ )
{
if ( x[j] <= y[j] ) t += y[j] - x[j];
else t += y[j] - x[j] + 26;
}
res = min ( res, t );
x.push_back ( x[0] );
x.erase ( x.begin() );
}
cout << res << endl;
}
}
时间复杂度 \(O(N^2)\ \ N≤50\)
E.Sequence
思维题
题面:
删除一个数,使得good数最大化。
good数解释:在一个排列数序列中,如果一个数的值比它前面的任意一个数大,则这个数就是good数。一个长度为\(n\)的排列数序列中最多存在\(n-1\)个good数
思路:
找到删除每个数的代价。
从头遍历数组,记录最小数和次小数。
如果\(a_i\)前面存在最小数或次小数,则\(a_i\)的代价自增\(1\)。
如果\(a_i\)前面存在最小数,且不存在次小数,则最小数的代价自增\(1\)。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int cnt[N], q[N];
void solve ( void )
{
memset ( cnt, 0, sizeof cnt );
int n;
cin >> n;
for ( int i = 0; i < n; i++ ) scanf ( "%d", &q[i] );
int minn = 0x3f3f3f3f, secminn = 0x3f3f3f3f;
for ( int i = 0; i < n; i++ )
{
if ( minn < q[i] || secminn < q[i] ) cnt[q[i]]++;
if ( minn < q[i] && secminn > q[i] ) cnt[minn]++;
if ( q[i] < secminn )
secminn = q[i];
if ( secminn < minn ) swap ( secminn, minn );
}
int res;
minn = 0x3f3f3f3f;
for ( int i = 1; i <= n; i++ )
if ( cnt[i] < minn ) res = i, minn = cnt[i];
cout << res << endl;
}
int main ( void )
{
int T;
cin >> T;
while ( T-- ) solve();
return 0;
}
算法复杂度 \(O(N)\)